题解 P1115 【最大子段和】

Hola_chen · 2019-01-26 15:43:23 · 题解

非喜勿喷~

#include<bits/stdc++.h>//万能头 
using namespace std;
int a[300001];//a是数组 
int f[300001];//f是做比较存储方案的数组 
int main()
{
    int n;//n 
    cin>>n;//输入n 
    for(int i=1;i<=n;i++)cin>>a[i];//循环输入a 
    for(int i=1;i<=n;i++)//for循环 
    {
        f[i]=-999999;//把f所有的赋为最小的数 
    }
    f[1]=a[1];//初始化 
    for(int i=2;i<=n;i++)//for循环 
    {
        f[i]=max(a[i],f[i-1]+a[i]);//状态转移方程，找最大方案 
    }
    int big=-999999;//做比较，先给big最小的值
    for(int i=1;i<=n;i++)//for循环比较大小 
    {
        if(f[i]>big)big=f[i];//if判断选取最大的方案 
    } 
    cout<<big<<endl;//输出最大的方案 
    return 0;//返回0 
}