最大子数组
题目描述
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
样例
样例1: 输入：[−2,2,−3,4,−1,2,1,−5,3] 输出：6 解释：符合要求的子数组为[4,−1,2,1]，其最大和为 6。 样例2: 输入：[1,2,3,4] 输出：10 解释：符合要求的子数组为[1,2,3,4]，其最大和为 10。
挑战
要求时间复杂度为O(n)
思路
动态规划：找到一个具有最大和的子数组，即找到包含第i个元素的连续子数组最大和，的最大值
状态转移方程
dp[i] = max(nums[i], nums[i] + dp[i - 1])
dp[i] = max(nums[i], nums[i] + dp[i - 1])
- i代表数组中的第i个元素的位置
- dp[i]代表从0到i闭区间内，所有包含第i个元素的连续子数组中，总和最大的值
代码：
#备忘录动态规划版本，空间复杂度为O（n） def maxSubArray(nums): # write your code here dp = [nums[0] for _ in range(len(nums))] for i in range(1,len(nums)): dp[i] = max(dp[i-1]+nums[i],nums[i]) return max(dp)
#迭代动态规划版本，空间复杂度为O（1） def maxSubArray(nums): # write your code here dp = nums[0] max_dp = nums[0] for i in range(1,len(nums)): dp = max(dp+nums[i],nums[i]) max_dp = max(max_dp,dp) return max_dp
投递腾讯等公司7个岗位
网易游戏公司福利 297人发布