Leetcode Problem 53 Maximum Subarray.txt

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.


Hint to solve: Maintain a globalMaxResult, counter for each element.
If the current element is greater than the counter reset the counter to current element.
If the globalMaxCounter is smaller than counter then reset the globalMaxCounter.

public class Solution {
    public int MaxSubArray(int[] nums) 
    {
        int globalMax = Int32.MinValue;
        int counter = 0;
        for(int i = 0; i<nums.Length; ++i)
        {
            int temp = counter + nums[i];
            counter = temp > nums[i] ? temp : nums[i];
            if(counter > globalMax)
            {
                globalMax = counter;
            }
        }
        
        return globalMax;
    }
}