53 Maximum Subarray

https://leetcode.com/problems/maximum-subarray/#/description

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

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.

分析及代码

• 思路

  • 维持一个局部最优和全局最优
  • 局部最优的含义是，必须选择当前这个元素，但是可以选择叠加在之前的元素上，或者从这个数新开始

• 初始化： 因为有可能包含负数，所以

  • 要么就把global和local的初始值设为Integer.MAX_VALUE
  • 要么就把第一个数单独处理，循环从1开始

public int maxSubArray(int[] nums) {
    if(nums.length == 0) {
        return 0;
    }
    int global = nums[0];
    int local = nums[0];
    for(int i = 1; i < nums.length; i++) {
        local = Math.max(local + nums[i], nums[i]);
        global = Math.max(global, local);
    }
    return global;
}

O(n)