Leetcode 53. Maximum Subarray [Medium]

Problem:

source: Maximum Subarray

Identify problem

We need to part contiguous part of the array that returns largest sum.

Approach

1. Brute Force: We Create one for loop(i) for iterating from start to end, another for loop(j) that starts from previous for loop(i) to the end, and another array that go through i and j to return largest sum. This is O(n^3) solution and not efficient.

2. Linear Solution: As we iterate through the list we keep record of past subarray’s result, and whenever when the past subarray is negative we don’t consider element in that past subarray and create new subarray starting from the current one.

Code

int maxSubArray(vector<int>& nums) {
        int cur = 0;
        int maxSub = nums[0];
        
        for(int i=0; i<nums.size(); ++i)
        {
            if(cur < 0)
            {
                cur = 0;
            }
            cur += nums[i];
            maxSub = max(maxSub, cur);
        }
        return maxSub;
    }

alteratively.

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