【编程测试题】连续最大和

题目描述

一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3

输入描述:

输入为两行。 第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素 第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。

输出描述:

所有连续子数组中和最大的值。

// 读完题的第一反应是动态规划。开始写了一个二维的，很好想，但是运行60%超时，

// 于是将二维改一维。这里我说一下我一维的思路，后面的代码是二维改一维后的代码

// ，思路是一样的。我们社dp[i]为第 i 个数与前面最大和数dp[i-1]之和的最大数，那么若

// dp[i] + dp[i-1] > dp[i]，dp[i]的值就应该是dp[i] + dp[i-1]；否则，是它本身，即dp[i]... ...

// 这样一直找到，然后找出dp[n]中最大的数字即可。如果不明白的话请结合下图思考：

// 代码如下：
#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
    int n, max;
    cin >> n;
    vector<int> list(n, 0), dp(list);
    for (int i = 0; i < n; i++)   //创建数组
        cin >> list[i];
    max = dp[0] = list[0];
    for (int i = 1; i < n; i++)   //由于是连续的，因此只需要更新对
    {                                     //角线即可，之前部分遇上一行相同
        if (list[i] + dp[i - 1] > list[i])      //如果上一对角线上的数和更大
            dp[i] = list[i] + dp[i - 1];       //填入对应位置
        else
            dp[i] = list[i];                       //否则，即为这个数本身
        if (max < dp[i]) max = dp[i];     //寻找数组中最大的
            
    }
    cout << max << endl;
    return 0;
}