砸金蛋
题目描述
Mike获得一个特技,“透视”,即不用打开箱子,就能看到箱子里有什么。于是他去参加砸金蛋的游戏,一根绳子上依序挂着n个金蛋,每个金蛋内有一个纸条,上面写了一个整数作为奖励,游戏参与者可以且仅可以选择绳子上的连续的一串金蛋,比如第二号到第五号。Mike利用特异功能已经先看到了所有金蛋内的纸条上的数值,请你帮他编写一个程序,找到一个起点和终点,使得Mike获得的奖励值最大。
输入格式
第一行输入一个正整数; 第二行有n个整数,是每个金蛋内的数字-32768 ≤ a[i] ≤ 32767。
输出格式
第一行有一个整数,表示起始位置编号。 第二行有一个整数,表示终止位置编号。 第三行有一个数,是奖励的和。 注:若有多个解,只输出起始位置编号最小的解,若多个解终止位置编号相同,则输出最小的编号。
输入样例:
5
-2 2 5 -1 6
输出样例
2
5
12
数据范围与提示
对于30%的数据,n<=100 对于60%的数据,n<=400 对于100%的数据,n<=1,000,000
信息
- ID
- 1000
- 难度
- 10
- 分类
- (无)
- 标签
- (无)
- 递交数
- 1
- 已通过
- 0
- 通过率
- 0%
- 上传者