Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) 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.

Problem Link

Maximum Subarray - LeetCode

Reference Video

https://www.youtube.com/watch?v=VMtyGnNcdPw

Code

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        int lm=0,gm=INT_MIN;
        
        for(int ele:nums) {
            lm = max(ele,lm+ele);
            gm = max(lm,gm);
        }
        return gm;
    }
};

Another Way

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int lm = nums[0],gm = nums[0];
        
        for(int i=1;i<n;i++)
        {
            lm = max(nums[i],nums[i]+lm);
            gm = max(lm,gm);
        }
        return gm;
        
    }
};

Time complexity O(n)

Space complexity O(1)