Maximum Subarray

• LeetCode: Maximum Subarray

• Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

• Examples:

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

• More practice:

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

• Analysis:

Declare two variables, global_Max and local_Max.

global_Max is to store maximum sum of subarray.

local_Max is to store maximum sum at nums[i]

• Code - Java:

class Solution {
    public int maxSubArray(int[] nums) {
        int global_Max = Integer.MIN_VALUE;
        int local_Max = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            local_Max = Math.max(local_Max + nums[i], nums[i]);
            global_Max = Math.max(global_Max, local_Max);
        }
        return global_Max;
    }
}

• Code - C++:

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

• Code - Python:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        global_Max, local_Max = (-1) * 2 ** 31, 0
        for num in nums:
            local_Max = max(local_Max + num, num)
            global_Max = max(global_Max, local_Max)
        return global_Max

• Time Complexity: O(N), N is the length of input array

• Space Complexity: O(1)