如何求最大子数组之和？（连续的子数组）

数据结构与算法

1.首发--简单动态规划

动态规划分两种，一种是人人为我，一种是我为人人。分析的关键就是最优子问题。这个最优可以有上一步的最优得到。

假设a数组长度为n。针对数组的最后一个元素有两种情况。

1. 一种是最大子数组包含最后一个元素
2. 一种是不包含。

这个不包含的话就好理解了，就要求的是[0,n-2]范围内的最大子数组。

要是包含的话又有两种情况：

1. a[n-1]单独成为最大子数组
2. a[n-1]非单独

非单独的情况就是以a[n-1]结尾的情况。end[n-1]

综上：数组a的最大子数组求解公式可以归纳为

$result[n-1]=max(a[n-1],end[n-1],result[n-2])$
$result[i]=max(a[i],end[i-1]+a[i],result[i-1])$

public class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] end = new int[len];
        int[] all = new int[len];
        //dp数组第一项和最后一项一定要给定，因为涉及到当前点，也就是最后结束的临界条件
        end[0] = all[0] = nums[0];
        end[len - 1] = all[len - 1] = nums[len - 1];
        for (int i = 1; i < len; i++) {
            //end数组表示的最大子数组和是一定包含最后一项的
            end[i] = Math.max(end[i - 1] + nums[i], nums[i]);
            //把包含最后一项和不包含最后一项的情况比划
            all[i] = Math.max(end[i], all[i - 1]);
        }
        return all[len - 1];
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, -2, 4, 8, -4, 7, -1, -5};
        System.out.println(solution.maxSubArray(nums));
    }
}

2.重构

public class Solution {
    public int maxSubArray(int[] nums) {
        int end = nums[0];
        int all = nums[0];
        for (int i = 1; i < nums.length; i++) {
            end = Math.max(end + nums[i], nums[i]);
            all = Math.max(end, all);
        }
        return all;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, -2, 4, 8, -4, 7, -1, -5};
        System.out.println(solution.maxSubArray(nums));
    }
}

首发应该是叫做记忆DP。主要是状态的保存