53. Maximum Subarray

Score : P(WITH BAD TIME COMPLEXITY) | Difficulty : Easy(BS)

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.

Answers from Solution:

Kadane's algorithm simpler to understand version O(n):

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

Greedy Implementation:

class Solution {
  public int maxSubArray(int[] nums) {
    int n = nums.length;
    int currSum = nums[0], maxSum = nums[0];

    for(int i = 1; i < n; ++i) {
      currSum = Math.max(nums[i], currSum + nums[i]);
      maxSum = Math.max(maxSum, currSum);
    }
    return maxSum;
  }
}


Dynamic Programming (Kadane's algorithm):

class Solution {
  public int maxSubArray(int[] nums) {
    int n = nums.length, maxSum = nums[0];
    for(int i = 1; i < n; ++i) {
      if (nums[i - 1] > 0) nums[i] += nums[i - 1];
      maxSum = Math.max(nums[i], maxSum);
    }
    return maxSum;
  }
}

M's n^2 solution:
class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int highestSum = Integer.MIN_VALUE;
        if(nums.length == 0){return Integer.MIN_VALUE;}
        for(int i = 0; i < nums.length; i++)
        {
            for(int j = i; j < nums.length; j++)
            {
                sum += nums[j];
                if(sum > highestSum)
                {
                    highestSum = sum;
                }
            }
            sum = 0;
        }
        return highestSum;
    }
}