Lintcode 41. Maximum Subarray

题目

Given an array of integers, find a contiguous subarray which has the largest sum.

Example Given the array [−2,2,−3,4,−1,2,1,−5,3], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

思路

基础版的subarray maximum sum，直接使用global/local dp求解。注意可以使用滚动指针优化空间复杂度。

复杂度

time O(n), space O(1)

代码

  public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        // write your code
        if (nums == null || nums.length == 0){
            return 0;
        }
        // preprocess
        int size = nums.length;
        int[] local = new int[size];
        int[] global = new int[size];
        local[0] = global[0] = nums[0];

        for (int i = 1; i < nums.length; i++){
            int cur = nums[i];
            local[i] = Math.max(local[i-1] + cur, cur);
            global[i] = Math.max(global[i-1], local[i]);
        }
        return global[size-1];
    }
}