洛谷 P1115 最大子段和

题目描述

给出一个长度为 nn 的序列 aa，选出其中连续且非空的一段使得这段和最大。

思路

1、一个数组用来记录输入的数据。
2、一个数组用来记录从0到i的子段和。
3、一个数组用来记录从0到i-1最小的子段和。
贪心的思路，因为当前子段和是由两个位置的子段和相减得到的。固定后端的位置i，只需要在小于i的前面选择一个最小的子段和减去，就可以保证当前的子段和是以i为后端的子段和中最大的子段和。

AC代码

#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int maxnumber = -20000, temp, number;
int alreadysum[200005], a[200005],minnumber[200005];
int main()
{
 ifstream in;
 //in.open("P1115_1.in");
 //in >> number;
 cin >> number;
 for (int i = 1; i <= number; i++)
 {
  cin >> a[i];
  //in >> a[i];
  alreadysum[i] = alreadysum[i - 1] + a[i];
  minnumber[i+1] = min(alreadysum[i], minnumber[i]);
 }
 //minnumber[1] = min(0, a[1]);
 for (int i = 1; i <= number; i++)
 {
  temp = alreadysum[i] - minnumber[i];
  if (temp > maxnumber)
   maxnumber = temp;
 }
 cout << maxnumber << endl;
 return 0;
}