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

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

解题思路

解法：
最简单的解法肯定是双层for循环，递归去找最大的子数组和，但是我们也知道，这个必定会超时的。仔细推导题目，发现这个好像是一个DP问题，是否可以找到状态转移方程呢？
1.我们定义，F(n)为以nums[n]数字结尾的子数组的，最大和，不难推导出F(n)与F(n-1)关系

当F(n-1)<=0时，F(n)=nums[n]
当F(n-1)> 0时，F(n)=nums[n] + F(n-1)
2.,F(n) = max(F(n-1)+nums[n],nums[n])

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
class Solution {
    public int maxSubArray(int[] nums) {
        // DP,F(n) = max(F(n-1)+nums[n],nums[n])
        // 我们定义，F(n)为以nums[n]数字结尾的子数组的，最大和，不难推导出F(n)与F(n-1)关系
        int pre = 0, max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            pre = Math.max(pre + nums[i], nums[i]);
            max = Math.max(max, pre);
        }
        return max;
    }
}