LeetCode 53. Maximum Subarray

53. Maximum Subarray

Difficulty:: Easy

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.

Solution

Language: Java

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

class Solution {
      public int maxSubArray(int[] nums) {
            if (nums == null || nums.length == 0) {
                  return 0;
           }
            int sum = 0;
            int[] preSum = new int[nums.length + 1];
            preSum[0] = 0;
            for (int i = 0; i < nums.length; i++) {
                  preSum[i + 1] = nums[i] + preSum[i];
           }
            int min = 0;
            int max = Integer.MIN_VALUE;
            for (int i = 1; i < preSum.length; i++) {
                  int s = preSum[i] - min;
                  if (s > max) {
                        max = s;
                 }
                  if (preSum[i] < min) {
                        min = preSum[i];
                 }
           }
            return max;
     }
}