解题思路

给定 n 天每天的收益（可正可负），需要从中选取一段连续天数，使这段连续收益之和最大，并输出这个最大收益。

这是典型的 最大子数组和 问题，可用 动态规划算法：

• 用 cur 表示“以当前天结尾的最大连续收益”
• 转移：cur = max(a[i], cur + a[i])

题目内容

团团过年收获了很多压岁钱，妈妈帮他开了账户去投资。现在给出 $n$ 天内投资收益情况，选出划中连续多少天的收益总和量大，这个收益是多少。

输入描述

第一行是一个整数 $n$ ，表示天数，$n$ 的范围为 $[0,1000]$

第二行是 $n$ 整数组成的一个数组，表示每天的收益，有正数也有负数，范围为 $[-10000,100000]$

输出描述

输出一个整数，表示选取的连续天数的收益

样例1

输入

3
1 0 -1

输出

1

说明

$3$ 天的收益，第一天最多，输出为 $1$

样例2

输入

7
2 -4 3 -1 2 -4 3

输出

4

说明

$7$ 表示 $7$ 天的收益，选取第 $3$ 天到第 $5$ 天的收益最大，$3-1+2=4$