思路概述
I、非常常规的动态规划问题，递推公式就是dp[i] = max(nums[i], nums[i] + dp[i-1])， 在当前i位置判断是否舍弃i及i前面的加和结果，比当前数字优就不舍弃， 即dp[i-1]得大于零，也就是历史结果得大于零才有延续下去的价值。
II、两个数组相互无法重叠，必定是一个在左，一个在右，那么从正反两个方向求出I中的dp_lift[i][0]、dp_right[i][0]记录从左、从右必定加上当前值情况下的局部最优解，dp_lift[i][1]、dp_right[i][1]记录从左、从右无论当前值加不加情况下的全局最优解。最后求出
max(dp_lift[i][1]+dp_right[i][1])
即可。
III、特殊动态规划问题，Local[i][j]表示在到达数组中第i个数时， 有j个子数组， 并且第i个数一定在子数组中，此为局部最优。Global[i][j]为在到达数组中第i个数时， 有j个子数组， 第i个数不一定在子数组中，此为全局最优。
Local[i][j] = max(Local[i-1][j], Global[i-1][j-1]) + nums[i-1]=max(Local[i-1][j]+ nums[i-1], Global[i-1][j-1]+ nums[i-1])
Local[i-1][j]+ nums[i-1]表示把第i个数加入到有着第i-1个数的第j个子数组，Global[i-1][j-1]+ nums[i-1]表示用第i个数新产生第j个子数组，max(Local[i-1][j]+ nums[i-1], Global[i-1][j-1]+ nums[i-1]) 表示对这种两种选择状态进行择优。
Global[i][j] = max(Local[i][j], Global[i-1][j])
特别注意，递推公式的max函数实际上代表了对过去状态产生的多个结果进行择优。
I
描述
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
子数组最少包含一个数。
样例
给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
代码
class Solution:
"""
@param nums: A list of integers
@return: A integer indicate the sum of max subarray
"""
def maxSubArray(self, nums):
# write your code here
dp = [0 for i in range(len(nums))]
dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(nums[i], nums[i] + dp[i-1])
return max(dp)
II
描述
给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
子数组最少包含一个数。
样例
给出数组 [1, 3, -1, 2, -1, 2]
这两个子数组分别为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]，它们的最大和都是 7
挑战
要求时间复杂度为 O(n)
代码
class Solution:
"""
@param: nums: A list of integers
@return: An integer denotes the sum of max two non-overlapping subarrays
"""
def maxTwoSubArrays(self, nums):
# write your code here
dp_lift = [[0, 0] for i in range(len(nums))]
dp_right = [[0, 0] for j in range(len(nums))]
dp_lift[0][0] = nums[0]
dp_lift[0][1] = nums[0]
for i in range(1, len(nums)):
dp_lift[i][0] = max(nums[i], nums[i] + dp_lift[i - 1][0])
dp_lift[i][1] = max(dp_lift[i][0], dp_lift[i - 1][1])
dp_right[-1][0] = nums[-1]
dp_right[-1][1] = nums[-1]
for i in reversed(range(0, len(nums) - 1)):
dp_right[i][0] = max(nums[i], nums[i] + dp_right[i + 1][0])
dp_right[i][1] = max(dp_right[i][0], dp_right[i + 1][1])
result = -10000
for i in range(0, len(dp_lift)-1):
result = max(result, dp_lift[i][1] + dp_right[i+1][1])
return result
III
描述
给定一个整数数组和一个整数 k，找出 k 个不重叠子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。
子数组最少包含一个数。
样例
给出数组 [-1,4,-2,3,-2,3] 以及 k = 2，返回 8
代码
class Solution:
"""
@param nums: A list of integers
@param k: An integer denote to find k non-overlapping subarrays
@return: An integer denote the sum of max k non-overlapping subarrays
"""
def maxSubArray(self, nums, k):
# write your code here
minNum = min(0, min(nums) - 1)
Local = [[0 for i in range(k + 1)] for i in range(len(nums) + 1)]
Global = [[0 for i in range(k + 1)] for i in range(len(nums) + 1)]
for j in range(1, k+1):
Local[0][j] = minNum
Global[0][j] = minNum
for i in range(1, len(nums)+1):
for j in range(1, k+1):
if j > i:
Local[i][j] = minNum
Global[i][j] = minNum
else:
Local[i][j] = max(Local[i-1][j], Global[i-1][j-1]) + nums[i-1]
Global[i][j] = max(Local[i][j], Global[i-1][j])
return Global[-1][-1]
题目来源
https://www.lintcode.com/problem/maximum-subarray-i/description
https://www.lintcode.com/problem/maximum-subarray-ii/description
https://www.lintcode.com/problem/maximum-subarray-iii/description
网友评论