题目描述

Mike获得一个特技，“透视”，即不用打开箱子，就能看到箱子里有什么。于是他去参加砸金蛋的游戏，一根绳子上依序挂着n个金蛋，每个金蛋内有一个纸条，上面写了一个整数作为奖励，游戏参与者可以且仅可以选择绳子上的连续的一串金蛋，比如第二号到第五号。Mike利用特异功能已经先看到了所有金蛋内的纸条上的数值，请你帮他编写一个程序，找到一个起点和终点，使得Mike获得的奖励值最大。

输入格式

输入格式 第一行输入一个正整数； 第二行有n个整数，是每个金蛋内的数字 -32768 ≤ a[i] ≤ 32767。

输出格式

输出 第一行有一个整数，表示起始位置编号。 第二行有一个整数，表示终止位置编号。 第三行有一个数，是奖励的和。 注：若有多个解，只输出起始位置编号最小的解，若多个解终止位置编号相同，则输出最小的编号。

样例

输入：

5
-2 2 5 -1 6

Copy

输出：

2
5
12

Copy

数据范围与提示

对于30%的数据,n<=100 对于60%的数据,n<=400 对于100%的数据,n<=1,000,000

反思总结：这道题需要考虑到全是负数、运算时间等情况。

做题的时候应该学习机器思维：将问题拆分成一个个小问题或者说是找到这个题目的做题根本点（这道题是只要不小于零都可以继续往下加），然后一步步求解。

做题时应该思考：什么时候才能把这个数算进去，如果数是负数会怎么样，如果全为负数又怎么样，全为正数呢等等问题。

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int n,sum=-10000005,start=1,en=1;
int a[1000005];
int main() {
    scanf("%d",&n);
    int temp=0,k=1;
    for(int i=1; i<=n; i++) {
        int t;
        scanf("%d",&t);
        temp+=t;
        if(sum<temp) {
            sum=temp;
            start=k;
            en=i;
        }
        if(temp<0) {
            temp=0;
            k=i+1;
            if(k==n+1)
                k=n;
        }
    }
    printf("%d\n%d\n%d\n",start,en,sum);
    return 0;
}