剑指 Offer 42. 连续子数组的最大和

题目描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

解题思路

这是一个典型的动态规划问题。
设f[n]表示以第n个数字为结尾的子数组的最大值。
有如下的状态方程：f[n] = max(nums[n], f[n-1] + nums[n])。
无初始状态和边界状态，需要注意的是以第0个为结尾的子数组是没有前一个数的。

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int result = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            f[i] = nums[i];
            if (i > 0) {
                f[i] = Math.max(f[i], f[i - 1] + nums[i]);
            }
            if (f[i] > result) {
                result = f[i];
            }
        }

        return result;
    }
}