目录
剑指 Offer 42. 连续子数组的最大和
easy
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
示例1:
|
|
DP
用 dp(i) 代表以第 i 个数结尾的「连续子数组的最大和」
dp(i) = max{ dp(i−1) + nums[i], nums[i] }
|
|
更简便的方法
因为 dp[i] 只与 dp[i-1] 相关,所以用一个 pre 变量接住 dp[i-1] 将空间复杂度降至 O(1)
|
|
easy
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
示例1:
|
|
用 dp(i) 代表以第 i 个数结尾的「连续子数组的最大和」
dp(i) = max{ dp(i−1) + nums[i], nums[i] }
|
|
因为 dp[i] 只与 dp[i-1] 相关,所以用一个 pre 变量接住 dp[i-1] 将空间复杂度降至 O(1)
|
|