题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805514284679168

这题主要有两点

  1. 特判全为负数的情况漏了
  2. 可以使用start数组记录最开始的下标

代码

  1. #include<vector>
  2. #include<cstdio>
  3. using namespace std;
  4. const int maxn = 10010;
  5. vector<int> number(maxn, 0), dp(maxn), start(maxn);
  7. int main(){
  8.     int n, max = 0; 
  9.     bool flag = false;
  10.     scanf("%d", &n);
  11.     for(int i = 0; i < n; i++) {
  12.         scanf("%d", &number[i]);
  13.         if(number[i] >= 0) flag = true;
  14.     }
  15.     if (flag == false){
  16.         printf("0 %d %d", number[0], number[n - 1]);
  17.         return 0;
  18.     }
  19.     dp[0] = number[0];
  20.     for(int i = 1; i < n; i++){
  21.         if(number[i] >= dp[i - 1] + number[i]){
  22.             dp[i] = number[i];
  23.             start[i] = i;
  24.         } else {
  25.             dp[i] = dp[i - 1] + number[i];
  26.             start[i] = start[i - 1];
  27.         }
  28.         if(dp[i] > dp[max]) max = i;
  29.     }
  30.     printf("%d %d %d" ,dp[max], number[start[max]], number[max]);
  31. }