给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 示例 2: 输入:nums = [1] 输出:1 示例 3: 输入:nums = [5,4,-1,7,8] 输出:23 提示: 1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4
解题思路:【贪心】
局部最优: 当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。 全局最优: 选取最大“连续和”
class Solution:
def max_sum_greedy(self, nums):
result = nums[0]
cur_sum = 0
for x in nums:
cur_sum += x
if cur_sum > result:
result = cur_sum
if cur_sum <= 0:
cur_sum = 0
return result
if __name__ == "__main__":
nums = list(map(int, input().split(',')))
solution = Solution()
result = solution.max_sublist_sum(nums)
print(result)
若需要打印数组,可以稍作改变
def max_sum_greedy(self, nums):
result = float('-inf') #存储最大和
cur_sum = 0
max_sublist= [] #存储和序列
max_sublist_index = [] #首尾存储区间下标
for i in range(len(nums)):
cur_sum += nums[i]
# 取区间累计的最大值(相当于不断确定最大子序终止位置)
if cur_sum >= result:
max_sublist_index.append(i)
result = cur_sum
# 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和
if cur_sum <= 0:
max_sublist_index.clear()
cur_sum = 0
# 中间可能存在负数,故仅存储正数下标
for i in range(max_sublist_index[0], max_sublist_index[-1] + 1):
max_sublist.append(nums[i])
return max_sublist
其他思路:【动态规划】
dp[i]表示i个元素前的最大连续和 dp[i] = max(dp[i - 1] + nums[i], nums[i])
def max_sum_dp(self, nums):
if len(nums) == 0:
return 0
dp = [None] * len(nums)
result = dp[0] = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i - 1] + nums[i], nums[i])
result = max(result, dp[i])
return result
其他思路:【暴力解法】
def max_sum_violence(self, nums):
result = nums[0]
for i in range(len(nums)):
cur_sum = 0
for j in range(i, len(nums)):
cur_sum += nums[j]
result = max(result, cur_sum) # 更新最大值
return result
仅作为代码记录,方便自学自查自纠
标签:cur,nums,max,sum,53,result,数组,leetcode,dp From: https://blog.csdn.net/weixin_45653183/article/details/142620329