剑指 Offer 42. 连续子数组的最大和
题目
剑指 Offer 42. 连续子数组的最大和 难度：easy
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)O(n)O(n)。
示例1:
代码语言：javascript复制输入: 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
方法一：动态规划
思路
假设 numstextit{nums}nums 数组的长度是 n，下标从 0 到 n−1。
我们用 f(i)f(i)f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：
max0≤i≤n−1{f(i)}max_{0 leq i leq n-1} { f(i) }0≤i≤n−1max{f(i)}
因此我们只需要求出每个位置的 f(i)f(i)f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i)f(i)f(i)呢？我们可以考虑 nums[i]textit{nums}[i]nums[i] 单独成为一段还是加入 f(i−1)f(i-1)f(i−1) 对应的那一段，这取决于 nums[i]textit{nums}[i]nums[i] 和 f(i−1) nums[i]f(i-1) textit{nums}[i]f(i−1) nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：
f(i)=max{f(i−1) nums[i],nums[i]}f(i) = max { f(i-1) textit{nums}[i], textit{nums}[i] }f(i)=max{f(i−1) nums[i],nums[i]}
不难给出一个时间复杂度 O(n)O(n)O(n)、空间复杂度 O(n)O(n)O(n) 的实现，即用一个 fff 数组来保存 f(i)f(i)f(i) 的值，用一个循环求出所有 f(i)f(i)f(i)。考虑到 f(i)f(i)f(i) 只和 f(i−1)f(i-1)f(i−1) 相关，于是我们可以只用一个变量 pretextit{pre}pre 来维护对于当前 f(i)f(i)f(i) 的 f(i−1)f(i-1)f(i−1) 的值是多少，从而让空间复杂度降低到 O(1)O(1)O(1)，这有点类似「滚动数组」的思想。
解题
Python：
代码语言：javascript复制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：
代码语言：javascript复制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∗nm*nm∗n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
代码语言：javascript复制输入:
[
[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)f(i, j)f(i,j) 为从棋盘左上角走至单元格 (i,j)(i ,j)(i,j) 的礼物最大累计价值，易得到以下递推关系：f(i,j)f(i,j)f(i,j) 等于 f(i,j−1)f(i,j-1)f(i,j−1) 和 f(i−1,j)f(i-1,j)f(i−1,j) 中的较大值加上当前单元格礼物价值 grid(i,j)grid(i,j)grid(i,j) 。
f(i,j)=max[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)f(i,j)=max[f(i,j−1),f(i−1,j)] grid(i,j)
因此，可用动态规划解决此问题，以上公式便为转移方程。
解题
Python：
代码语言：javascript复制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：
代码语言：javascript复制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];
}
}
