【动态规划】1.线性DP

GALA-Lin2025/4/23大约 2 分钟

系列文章

线性DP（Linear DP）是指在一维数组上进行的动态规划，即数组的每个元素只与前一个元素有关，而与其他元素无关。

给定一个整数数组，求该数组的最大子序和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

给定一个整数数组，求该数组的最大子数组和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：7
解释：连续子数组 [4,-1,2,1] 的和最大，为 7。

给定一个整数矩阵，求该矩阵的最大子矩阵和。

输入：matrix = [[1,0,-1],[2,-1,3],[-1,2,-1]]
输出：3
解释：子矩阵 [[2,-1,3],[-1,2,-1]] 的和最大，为 3。

给定一个整数矩阵，求该矩阵的最大子矩阵和，且该子矩阵必须是连续的。

输入：matrix = [[1,0,-1],[2,-1,3],[-1,2,-1]]
输出：2
解释：子矩阵 [[1,0,-1],[2,-1,3]] 的和最大，为 2。

给定一个整数矩阵，求该矩阵的最大子矩阵和，且该子矩阵必须是不重叠的。

输入：matrix = [[1,0,-1],[2,-1,3],[-1,2,-1]]
输出：4
解释：子矩阵 [[1,0],[-1,2]] 和 [[2,-1,3]] 的和最大，为 4。

线性DP问题的时间复杂度都为 $O(n)$ ，其中 $n$ 为数组的长度。