题目

剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

提示：

1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
注意：本题与主站 53 题相同

思路

既然要时间复杂度O(n)，只能循环一次，那么其实我们可以知道，我求当前的最大子数组和必定和前面一个的和有必然联系，那么我们这样想，从第一个开始，我以当前数作为最小子数组的末尾值，那么当前的最大值就是自己，而下一个的计算肯定就是Max(当前值，当前值+前面的子数组最大值)，这样状态转移方程就出来了
f(i) = max(f(i),f(i)+f(i-1))
于是就可以轻松写下如下代码，秒过。

代码

package leetcode.offer.q42;

public class Solution {
    public int maxSubArray(int[] nums) {
        int[] maxSums = new int[nums.length];
        maxSums[0] = nums[0];
        int max = maxSums[0];
        for (int i = 1,len = nums.length; i < len;i++){
            if (maxSums[i-1] > 0){
                //前面的能让我增加
                maxSums[i] = maxSums[i-1] + nums[i];
            }else {
                //前面的让我更小了我还不如就我自己
                maxSums[i] = nums[i];
            }
            if (maxSums[i] > max){
                max = maxSums[i];
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(new Solution().maxSubArray(nums));
    }
}