剑指 Offer 42. 连续子数组的最大和
题目
剑指 Offer 42. 连续子数组的最大和 难度：easy
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 $O(n)$。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。提示：
1 <= arr.length <= 10^5-100 <= arr[i] <= 100
方法一：动态规划
思路
假设 $\textit{nums}$ 数组的长度是 n，下标从 0 到 n−1。
我们用 $f(i)$ 代表以第 i 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：
$$ \max_{0 \leq i \leq n-1} \{ f(i) \} $$
因此我们只需要求出每个位置的 $f(i)$，然后返回 f 数组中的最大值即可。那么我们如何求 $f(i)$呢？我们可以考虑 $\textit{nums}[i]$ 单独成为一段还是加入 $f(i-1)$ 对应的那一段，这取决于 $\textit{nums}[i]$ 和 $f(i-1) + \textit{nums}[i]$ 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：
$$ f(i) = \max \{ f(i-1) + \textit{nums}[i], \textit{nums}[i] \} $$
不难给出一个时间复杂度 $O(n)$、空间复杂度 $O(n)$ 的实现，即用一个 $f$ 数组来保存 $f(i)$ 的值，用一个循环求出所有 $f(i)$。考虑到 $f(i)$ 只和 $f(i-1)$ 相关，于是我们可以只用一个变量 $\textit{pre}$ 来维护对于当前 $f(i)$ 的 $f(i-1)$ 的值是多少，从而让空间复杂度降低到 $O(1)$，这有点类似「滚动数组」的思想。
解题
Python：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
nums[i] += max(nums[i - 1], 0)
return max(nums)Java：
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];
for (int x : nums) {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
}
return maxAns;
}
}
剑指 Offer 47. 礼物的最大价值
题目
剑指 Offer 47. 礼物的最大价值 难度：medium
在一个 $m*n$ 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物提示：
0 < grid.length <= 2000 < grid[0].length <= 200
方法一：动态规划
思路
根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达。
设 $f(i, j)$ 为从棋盘左上角走至单元格 $(i ,j)$ 的礼物最大累计价值，易得到以下递推关系：$f(i,j)$ 等于 $f(i,j-1)$ 和 $f(i-1,j)$ 中的较大值加上当前单元格礼物价值 $grid(i,j)$ 。
$$ f(i,j) = \max[f(i,j-1), f(i-1,j)] + grid(i,j) $$
因此，可用动态规划解决此问题，以上公式便为转移方程。
解题
Python：
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
for j in range(1, n): # 初始化第一行
grid[0][j] += grid[0][j - 1]
for i in range(1, m): # 初始化第一列
grid[i][0] += grid[i - 1][0]
for i in range(1, m):
for j in range(1, n):
grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
return grid[-1][-1]Java：
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
for(int j = 1; j < n; j++) // 初始化第一行
grid[0][j] += grid[0][j - 1];
for(int i = 1; i < m; i++) // 初始化第一列
grid[i][0] += grid[i - 1][0];
for(int i = 1; i < m; i++)
for(int j = 1; j < n; j++)
grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
return grid[m - 1][n - 1];
}
}
后记
📝 上篇精讲： 【算法题解】 Day23 搜索与回溯
💖 我是 𝓼𝓲𝓭𝓲𝓸𝓽，期待你的关注；
👍 创作不易，请多多支持；
🔥 系列专栏： 算法题解
