53. Maximum Subarray

 
Maximum Subarray

Problem Description

Given an integer array nums, find the subarray which has the largest sum, and return its sum.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) the solution, try coding another solution using the divide-and-conquer approach, which is more subtle.

Approach) Kadane`s Algo

var maxSubArray = function(nums) {
    let sum = 0;
    let maxSum = -Infinity;
    
    if(nums.length === 0) return 0;
    if(nums.length === 1) return nums[0]
    
    for(let i = 0;i<nums.length;i++){
        sum+=nums[i];
        maxSum = Math.max(maxSum,sum);
        if(sum < 0) sum = 0;
    }
    return maxSum;
};

Approach) DP 

const maxSubArray = (a) => {
    let n = a.length;
    let dp = Array(n).fill(0); // save max suarray sum ending with a[i]
    dp[0] = a[0];
    for (let i = 1; i < n; i++) {
        if (dp[i - 1] < 0) { // (dp[i-1]: pre max subarray sum) < 0, drop previous, new subarray sum start from a[i]
            dp[i] = a[i];
        } else { // >= 0  add previous to new subarray sum
            dp[i] = dp[i - 1] + a[i];
        }
    }
    return Math.max(...dp);
};

clean version merge if else

const maxSubArray = (a) => {
    let n = a.length;
    let dp = Array(n).fill(0);
    dp[0] = a[0];
    for (let i = 1; i < n; i++) dp[i] = Math.max(dp[i - 1], 0) + a[i];
    return Math.max(...dp);
};

Approach) Native 

let maxSubArray = function(nums) {
    let max1 = nums[0];
    let max2 = nums[0];
    for(let i=1; i<nums.length; i++){
        max1 = Math.max(nums[i] , max1 +nums[i])
        
        if(max1 > max2){
            max2 = max1;
        }
    }
    return max2;
};

Approach) Native Javascript

const maxSubArray = nums =>
  nums.reduce(
    ([localMax, globalMax], curr) => [
      Math.max(curr, localMax + curr),
      Math.max(curr, localMax + curr, globalMax),
    ],
    [-Infinity, -Infinity],
  )[1];

Conclusion

That’s all folks! In this post, we solved LeetCode problem 53. Maximum Subarray

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!