# Maximum Subarray sum

• 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.

• Look good to me.

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