1. 前言

动态规划（Dymamic Programming，简称 DP）应该是面试中出现频率最多并且公认难度最大的一类题型，动态规划问题非常灵活，没有统一的模板。动态规划中最简单的问题，例如爬楼梯，状态转移方程非常简单，但是大部分问题都没有通用的状态转移方程，所以如果缺乏对DP问题的练习，在笔试和面试中就有卡壳无从下手的风险。候选人的目标应该是尽可能的找到不同题目之间的相似点并举一反三。

2. 最大子数组和

面试官提问：给定一个数组，求解数组中连续子树组的最大和。

题目解析：

求解最大子数组求和问题是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/maximum-subarray/。

我们以小型数据的数组作为样例分析，什么是连续子数组的最大和：

样例输入：[-2,1,-3,4,-1,2,1,-5,4]

样例输出：6

样例解释：连续子数组 [4,-1,2,1] 的和最大，求和结果为6。

这里需要特别明确子树组和子序列的区别，

（1）子树组定义：一个或者连续多个数组中元素组成一个子数组；
（2）子序列定义：在原来数组中找出一部分组成的序列。

结论：子树组一定是连续的数字，但是子序列只需要保证前后顺序上的有序，数字之间不一定连续。

在明确子数组定义之后，我们用一句话概括 DP 的核心解题思路：我们要找到某个子问题的最优解，然后在它的帮助下，找到下一个子问题的最优解。

例如对于爬楼梯问题，对于 n 个台阶，每次能够跳一个台阶或者两个台阶，我们知道对于第 k 个台阶，一定是从第 k-1 个台阶再跳一个台阶，或者是从第k-2个台阶再跳两个台阶上来，所以只需要知道第 k-1 个台阶的路径个数和第k-2个台阶的路径个数，求和就是最终的答案。其中第 k-1 和第 k-2 个台阶的路径就是子问题。

将上述的语义切换到算法上来，就是需要找到状态转移方程以及状态的初始值。

最大子树组和问题中，状态的初始含义非常明确：如果数组的长度为空，那么不存在子树组，直接返回最大和为零。

初始状态结果为零的含义是，最后返回的最大子树组和一定不是负数，因为和为负数还不如直接用空数组返回零。

对于一般子问题，我们假设 dp[i] 表示以 nums[i] 作为子树组末尾元素的前i个数字构成的子树组的最大和，nums[i]表示数组中的第i个元素。举例来说，对于数组[a1，a2，a3]，dp[2] 只有三种构成可能：[a1，a2，a3]，[a2，a3]，[a3]，都是以 a3 作为子数组结尾元素。

那么假设已经遍历到了第i个数字，如果 dp[i-1] 小于零，说明数组的前 i-1 个子树组的和最大也是负数，前面说过，负数对于求解结果是没有帮助的，所以如果 dp[i-1] 小于零，dp[i] 直接选择 nums[i] 作为只有一个元素的子数组，和最大值就是 nums[i]。如果 dp[i-1] 大于零，说明加上前面的子树组会让结果更大，那么需要加上。

上面的语义用dp方程表示如下：

dp[i] = 0 如果nums.length=0；

dp[i] = nums[i] 如果dp[i-1] < 0；

dp[i] = nums[i] + dp[i-1]，如果dp[i-1] > 0 。

最后，我们需要返回的是 dp 数组中的最大值。

从状态转移方程可以看出，我们其实只需要 dp[i-1]，所以使用一个临时变量去保存它，能将空间复杂度降低到O（1）。示例：

public int maxSubArray(int[] nums) {
    //边界条件判断
    if (nums.length == 0){
        return 0;
    }
    //表示dp[i-1]
    int prev = nums[0];
    //表示dp[i]
    int cur = nums[0];
    //结果
    int max = nums[0];
    
    for (int i = 1; i < nums.length; i++){
        if (prev > 0){
            //如果dp[i-1] > 0
            cur = prev + nums[i];
        } else {
            //如果dp[i-1] <= 0
            cur = nums[i];
        }
        max = Math.max(max, cur);
        prev = cur; 
    }
    
    return max;
}

3. 小结

本章节介绍了动态规划中最简单的一种问题，就是在数组中找到满足要求的极大值或者极小值，通常只需要构建一个简洁的状态转移方程就可以解决问题。如果状态转移方程中只涉及到连续的两个或者三个位置的值变化，甚至可以将状态数组压缩到单个变量，将空间复杂度从O（n）优化到O（1）。