力扣AC：最大子数组和 - 动态规划

题目链接

最大子数组和

题目描述

实现代码

思路：由题意可知，第i个位置的字符串对应的最大连续子数组和肯定是与第i-1个位置的字符串对应的最大连续子数组和有关，关系就在于是否取当前值nums[i]，什么时候取nums[i]呢，假设f[i]表示第i个位置的字符串对应的最大连续子数组和，那么当f[i-1] + nums[i] > nums[i]的时候，就取nums[i]，否则，取nums[i]得到的结果比nums[i]本身还小，那取就没有必要了，其状态转移方程也可以写成如下形式：

f[i] = Math.max(f[i-1] + nums[i], nums[i]);

实现代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 1) {
            return  nums[0];
        }
        int result = nums[0];
        int current = nums[0];
        for(int i=1; i<len; i++) {
            if(current + nums[i] < nums[i]) {
                current = nums[i];
            } else {
                current += nums[i];
            }
            result = Math.max(result, current);
        }
        return result;
    }
}