题目描述

给定一个整数数组nums，请找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入描述

第一行输入一个整数n，表示数组长度，1 <= n <= 100000。
第二行输入n个整数，表示数组nums，每个数的范围是-10000到10000。

输出描述

输出一个整数，表示最大连续子数组和。

示例 1

输入：

text

9 -2 1 -3 4 -1 2 1 -5 4

输出：

text

6

解释：连续子数组[4, -1, 2, 1]的和最大，为6。

示例 2

输入：

text

1 -1

输出：

text

-1

解题思路

这是经典的 Kadane 算法。

设dp[i]表示以nums[i]结尾的最大连续子数组和：

text

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

答案为所有dp[i]中的最大值。由于状态只依赖前一个状态，可以用一个变量滚动更新。

参考代码

def solve(): n = int(input().strip()) nums = list(map(int, input().split())) cur = nums[0] ans = nums[0] for i in range(1, n): cur = max(nums[i], cur + nums[i]) ans = max(ans, cur) print(ans) if __name__ == "__main__": solve()