连续子数组最大和

题目描述

输入一个整形数组（可能有正数和负数），求数组中连续子数组（最少有一个元素）的最大和。要求时间复杂度为O(n)。

输入描述:

第一行为数组的长度N（N>=1） 接下来N行，每行一个数，代表数组的N个元素

输出描述:

最大和的结果

这个题会让有的同学的第一反应不对，例如，有的同学就会认为连续的最大子数组和肯定就是连续的正数之和，遍历整个数组。当遇到正数加给tmp，当遇到了负数将tmp和max比较。数组结束，max也就是最大的连续子数组和。这次一种错误的思路。虽然说你的隔壁可能是负数，但是你的隔壁的隔壁更大，足以抵消掉整个负数。我们正确的思路应该是下面这几种。

这个题一共有三种解法

1、穷举法。
2、循环法。
3、动态规划。

在这里，我们细细讲解。
1、穷举法就是讲该数组的所有子数组全部求出他们各自的和，然后进行比较，比较简单，这里都不列代码了。
2、定义一个tmp为数组的第一个元素，在第二个元素开始，将tmp和此元素的和与0进行比较，小于0则说明前面的元素都没有用了，重新将此元素赋值给tmp，大于0则说明前面的元素还是有用的，这里的前面的元素指的是没有过小于0的最前面那个元素开始到当下tmp所加的元素的位置。不懂的同学，看下图，会一目了然。

然后，我们再把代码附在下面。``

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin>>n;
    vector<int> v(n, 0);
    for(int i = 0;i<n;i++)
    {
        cin>>m;
        v[i] = m;
        //v.push_back(m);
    }
    int max = v[0];
    int tmp = v[0];
    for(int i = 1;i<n;i++)
    {
        if(tmp<=0)
            tmp = v[i];
        else
            tmp+=v[i];
        if(tmp>max)
            max = tmp;
    }
    cout<<max;
    return 0;
}

3、接下来，我们再谈一下该题动态规划的做法。
动态规划是啥这里就不讲了。
动态规划的其实就是找到上一次与本次之间的关系。
在这里，我们首先看下图，在细细讲解。

有的同学看到我图片里写的文字有点懵，我解释一下，上面那个数组是原数组，下面那个数组是我新创建。用于存放动态规划方法所得来的值。当前位置指的就是下面那个数组的每一个位置。这个位置是在数组的第二个位置开始算起。
下面数组的每个元素的内容代表着原数组从0位置到当前对应的上面数组的位置的最大的连续子数组和。
为什么这么说呢？
第一个元素不用说，直接用的就是原数组的第一个元素。第二个元素开始，当下面数组的第一个元素与上面数组的第二个元素的和与上面数组第二个元素进行比较。大着就是上面数组0到第二个元素的连续子数组最大和。以后一次类推。最终遍历下面数组就得到了最大的连续数组和。再将代码附着到下面。

#include<bits/stdc++.h>
using namespace std;
void Func(vector<int> v, vector<int>& dp)
{
    dp[0] = v[0];
    for(size_t i = 1;i<v.size();i++)
    {
        dp[i] = max(v[i]+dp[i-1], v[i]);
    }
}
int main()
{
    int n, m;
    cin>>n;
    vector<int> v(n, 0);
    for(int i = 0;i<n;i++)
    {
        cin>>m;
        v[i] = m;
        //v.push_back(m);
    }
    vector<int> dp(n, 0);
    int max = v[0];
    Func(v, dp);//动态规划函数
    for(int i = 0;i<n;i++)
    {
        if(dp[i]>max)
            max = dp[i];
    }
    cout<<max;
    return 0;
}

谢谢大家！！！