53. Maximum Subarray Sum / Kadane

Problem Statement

Given an integer array nums, find the

subarray with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

• 1 <= nums.length <= 105

• -104 <= nums[i] <= 104

Intuition

"Very efficient solution to find maximum subarray sum
        
Intuition- negative nos are not carried forward in the sum  
only positive are carried forward
"

Links

https://leetcode.com/problems/maximum-subarray/

Video Links

https://www.youtube.com/watch?v=w_KEocd__20&list=PLgUwDviBIf0rPG3Ictpu74YWBQ1CaBkm2&index=6

Approach 1:

Kadane Algorithm

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum=0;
        int maxi=nums[0];
        int n=nums.size();

        for(int i=0;i<n;i++){
            sum+=nums[i];

            if(sum>maxi)
                maxi=sum;
            // We dont want to carry forward the negative sum as it will lead to
            // neg sum as we go
            if(sum<0)
                sum=0;
        }

        return maxi;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++

Similar Problems