题解 | #连续子数组最大和#

连续子数组最大和，算是最简单的动态规划题目；从设计上来说，需要一个动态递归方程，以及一个参数表；但实际上这部分的存储可以优化掉。

#include <iostream>
using namespace std;
int main() {
    int N;
    while(cin >> N) {
        // 动态规划算法
        // 设dp[i] 为以i往后的连续子数组最大和；
        // 那么dp[i] = max(dp[i-1]+nums[i], nums[i])
        // 最后的输出结果是在dp中找最大的连续子数组和输出。
        int max_sum = INT16_MIN;
        int dp_sum = 0;
        while (N--) {
            int num;
            cin >> num;
            dp_sum = max(dp_sum + num, num);
            max_sum = max(dp_sum, max_sum);
        }
        cout << max_sum << endl;
    }
    return 0;
}