【每日训练】连续最大和

目录

题目链接：

​编辑测试用例：

解析：

程序：

---

题目链接：

连续最大和_牛客题霸_牛客网 (nowcoder.com)

测试用例：

解析：

题目描述：

        求一个数组中连续数（一个子数组）中最大的值。

思路：

        本题着力于子数组。子数组也就是此数组里任意的连续数据，此数组可以是1个数据也可以是多个数据。并且子数组也可以是本身。只要连续之和最大即可。

        因为是连续，所以最好想的就是以每个位置开始，分成不同的子段，每段累加进行比较，求得最大后转到下一个位置继续比较......这种虽然好想，但是时间复杂度O(N^2)，效率低下。

                                                

        那么能不能在只遍历一遍此数组的情况下（时间复杂度为O(N)）达到求得其最大连续和呢？

        这个时候只有动态规划了。（动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。--百度百科）

        其实，从连续这个字眼我们可以扣出来。因为既然是求连续的，那么每次遍历时我把当前下标的值加上前一个下标的值，遍历到最后不就可以求的这个连续的数的和了吗。和是能求，但是现在是要求最大值。那么我们就可以在遍历的过程中规划一下路径，只要前一个不为负（为负的话前面的连续和已经小了，不需要加在新的数上，从此数开始就是一个新的子数组），我们就加上。然后每次在累加时记录下max，如果比max大就需要记录一下。这样遍历一遍的同时做到了求连续子数组的和。

     

 

程序：

         如上分析所示，我们在遍历的时候可以直接对数组的值进行修改，达到记录当前子数组最大值的效果。但是如果原地修改数组的话，在不开辟新数组的空间前提下，下面程序分为了直接修改和不修改的版本，仅供参考~

修改数组值：

#include 
#include 
using namespace std;
 
int isMax(vector<int>& v)
{
    int max = v[0];
    for (int i = 1; i < v.size(); ++i)
    {
        if (v[i-1] > 0) v[i] += v[i - 1];  // 查看是否拖后腿，没拖后腿就继续连续，否则就分开到下一个连续数
        if (v[i] > max) max = v[i];  // 大就记录一下
    }
    return max;
}
 
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < v.size(); ++i)
    {
        cin >> v[i];
    }
 
    //动态规划-连续最大和
    cout << isMax(v) << endl;
    return 0;
}

不修改：

#include 
#include 
using namespace std;
 
int isMax(int a, int b)
{
    return a > b ? a : b;
}
 
int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < v.size(); ++i)
    {
        cin >> v[i];
    }
 
    //动态规划-连续最大和
    int max = v[0];
    int sum = v[0];  // 统计子数组的连续最大值
    for (int i = 1; i < v.size(); ++i)  // 没有修改原数组的值
    {
        sum = isMax(sum + v[i], v[i]);
        if (sum > max) max = sum;
    }
    cout << max << endl;
    return 0;
}

嘿嘿，知道我要说什么了吧：______________!