#P3009. [USACO11JAN] 利润
[USACO11JAN] 利润
题目描述
奶牛们开始了新的生意,它们的主人约翰想知道它们到底能做得多好。这笔生意已经做了N(1≤N≤100,000)天,每天奶牛们都会记录下这一天的利润Pi(-1,000≤Pi≤1,000)。
约翰想要找到奶牛们在连续的时间期间所获得的最大的总利润。(注:连续时间的周期长度范围从第一天到第N天)。
请你写一个计算最大利润的程序来帮助他。
输入格式
*第1行:单个整数:N *第2..N+1:第i+1行包含一个整数:P_i
输出格式
*第1行:单个整数,表示任何连续时间段的最大利润总和的值。
7
-3
4
9
-2
-5
8
-3
14
提示
取第二个到第六个数字(4,9,-2,-5,8)的和=>14,得到最大和。