PAT甲級真題1007. Maximum Subsequence Sum

題目連結：https://www.patest.cn/contests/pat-a-practise/1007

題意：給我們n個數，讓我們輸出這n個數中連續和最大的一段的和，以及這段的起始的數和結尾的數(注意是輸出數不是下标)，如果所有數都是負數，那麼我們輸出最大和0并輸出第1個數和第n個數。

首先我們可以分析複雜度，n的範圍是10000，那麼n^2的周遊的複雜度應該能夠過，是以直接存儲字首和，再進行n^2暴力周遊應該是可行的。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000+5;
int a[maxn];
int main() {
  int n;
  scanf("%d", &n);
  int flag = 0;
  for(int i=0; i<n; i++) {
    cin >> a[i];
    if(a[i] >= 0) flag = 1;
  }
  if(!flag) {
    printf("0 %d %d\n", a[0], a[n-1]);
    return 0;
  }
  int sum = 0, Max = 0;
  int l, r, Ml;
  l = Ml = 0;
  r = n-1;
  for(int i=0; i<n; i++) {
    sum += a[i];
    if(sum > Max || (sum == 0 && r == n-1)) {
      Max = sum;
      r = i;
      Ml = l;
    }
    if(sum <= 0) {
      sum = 0;
      l = i+1;
    }
  }
  printf("%d %d %d\n", Max, a[Ml], a[r]);
}