给定一个整数数组，找到一个具有最大和的连续子数组

解法1：暴力枚举

通过枚举所有的连续子数组，计算它们的和，最后返回最大的和。

时间复杂度：O(n^2)

代码：

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float('-inf')
for i in range(len(nums)):
cur_sum = 0
for j in range(i, len(nums)):
cur_sum += nums[j]
if cur_sum > max_sum:
max_sum = cur_sum
return max_sum

解法2：动态规划

我们可以用 dp[i] 表示以第 i 个元素结尾的最大连续子数组的和，那么 dp[i] 可以由 dp[i-1] 转移得到：

dp[i] = max(dp[i-1] + nums[i], nums[i])

时间复杂度：O(n)

代码：

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
max_sum = nums[0]
for i in range(1, len(nums)):
dp[i] = max(dp[i-1] + nums[i], nums[i])
max_sum = max(max_sum, dp[i])
return max_sum

解法3：分治法

将数组分成左右两部分，分别求出左半部分的最大子数组、右半部分的最大子数组以及跨越中心的最大子数组，最后返回三者中的最大值。

时间复杂度：O(nlogn)

代码：

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
return self.helper(nums, 0, len(nums)-1)

def helper(self, nums, left, right):
if left > right:
return float('-inf')
mid = (left + right) // 2
left_max = self.helper(nums, left, mid-1)
right_max = self.helper(nums, mid+1, right)
cross_max = self.crossMax(nums, left, mid, right)
return max(left_max, right_max, cross_max)

def crossMax(self, nums, left, mid, right):
left_max = float('-inf')
cur_sum = 0
for i in range(mid, left-1, -1):
cur_sum += nums[i]
left_max = max(left_max, cur_sum)
right_max = float('-inf')
cur_sum = 0
for i in range(mid+1, right+1):
cur_sum += nums[i]
right_max = max(right_max, cur_sum)
return left_max + right_max

解法4：贪心算法

我们可以从左到右遍历数组，记录当前连续子数组的和 cur_sum 和最大连续子数组的和 max_sum，如果 cur_sum 加上下一个数 nums[i] 小于 nums[i]，那么从 nums[i] 开始重新计算 cur_sum。每次更新 max_sum，最后返回 max_sum 即可。

时间复杂度：O(n)

代码：

class Solution:
def maxSubArray(self, nums: List[int]) -> int:
cur_sum = max_sum = nums[0]
for i in range(1, len(nums)):
cur_sum = max(nums[i], cur_sum+nums[i])
max_sum = max(max_sum, cur_sum)
return max_sum