Maximum Subarray sum


  • 0
    M

    Let's say if array only contains +ve numbers, in this case maximum subarray will be sum of complete array itself ( which is quite obvious ) .

    But what if array contains some -ve or all -ve numbers. So, summation of all numbers will not guarantee us maximum subarray. We now need to think of solution that will help us get maximum subarray.

    Can be obvious for someone

    Subarray : Contiguous elements in an array.

    Subsequence : May not be contiguous, but occur in order.

    ( or to be more technical )

    Subsequence are derived from another sequence by deleting some elements without changing the order of the remaining elements.
    example
    [1,4,5] is subsequence of array [1,2,3,4,5]
    [3,1,5] is not subsequence of array [1,2,3,4,5].

    Code for the solution

    public int MaxSubArray(int[] nums) {
          var globalMaximum = nums[0];
          var maximumSoFar = nums[0];
          var length = nums.Length;
            
          for(var i=1; i<length; i++){
              maximumSoFar = Math.Max(nums[i] + maximumSoFar, nums[i]);
              globalMaximum = Math.Max(globalMaximum, maximumSoFar);
          }
            
          return globalMaximum;    
    
        }
    
    

    Steps to solve it.

    • Initialise globalMaximum and maximumSoFar to first array element.

    • Loop through elements and keep track of maximum sum till current traversal pointer.

    • Swap with globalMaximum if maximumSoFar becomes greater than globalMaximum.

    Time Complexity : O(n)
    Space Complexity : Constant ( as we are using only 3 variables )

    Let take this example, here maximum subarray sum is 11.

    0_1502527180864_Screen Shot 2017-08-12 at 2.07.05 PM.png


  • 0
    R

    Look good to me.


Log in to reply
 

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