With Explanation of how it works..


  • 0
    L

    This is an interesting example to understand how to apply inductive approach.

    Imagine I know the maximum sum of subarray a[0...i1], let it be mx. Let cursum be the one under consideration.
    On seeing the next a[ i ] element, it will either increase cursum or decrease it.

    If it increases, then we expand the array. simple. cursum +a[I].

    If it decrements cursum, then we have to think, should we add it to cur array or not
    a) We can add it if its still positive. cursum + a[i] and there is a hope that a positive number can follow.
    b) We should not add it if cursum + a[I] becomes negative or less than a[I], so lets take cursum to be a[I].

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.