题解 | #最大序列和#

动态规划求解（暴力解会超时）

#include <climits>
#include <iostream>
using namespace std;
/*
动态规划：dp[i]存的是以a[i]为结尾的连续子序列的和
*/
int main(){
    int n;
    while (cin >> n){
        int a[n], dp[n];
        for (int i = 0; i < n; i++){
            cin >> a[i];
        }

        dp[0] = a[0];
        int m = a[0];
        for (int i = 1; i < n; i++){
            dp[i] = max(dp[i-1]+a[i],a[i]);
            if (m < dp[i]) m = dp[i];
        }
        cout<< m<<endl;
    }
}

/*暴力解 运行超时
int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case

        int a[n],max = INT_MIN,temp = 0;
        for (int i = 0; i < n; i++){
            cin >> a[i];
            
        }
        
        for (int i = 0; i < n; i++){
            temp = 0;
            for (int j = i; j < n; j++){
                temp += a[j];
                if (max < temp){
                    max = temp;
                }
               // cout<<j<<" "<<max<<" "<<temp<<endl;
            }
            
        }
        cout << max << endl;
    }
}*/
// 64 位输出请用 printf("%lld")