连续子数组最大和

连续子数组最大和

一、暴力循环

时间复杂度O(n^2)，空间复杂度O(1)，不过运行会超时。

/*
2022年09月10日 12:50:06
暴力循环
时间复杂度O(n^2)，空间复杂度O(1)，不过运行会超时。
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];
    int maxSum = v[0];
    for(size_t i = 1; i < n; ++i)
    {
        int sum = 0;
        for(size_t j = i; j < n; ++j)
        {
            sum += v[j];
            maxSum = max(sum, maxSum);
        }
    }
    cout << maxSum << endl;
    return 0;
}

二、dp

时间复杂度O(n)，空间复杂度O(n)

/*
2022年09月10日 11:42:23
dp[i]是以数组下标为 i 的数做为结尾的最大子序列和，注意是以 i 为结尾
比如说现在有一个数组 {6,-3,-2,7,-15,1,2,2}
dp[2]就是以-2为结尾的，那么显然dp[2]的最大值就是1（6，-3，-2），
dp[3]要以7结尾，那么以7结尾的子序列最大和就是8（6，-3，-2，7）。
求dp[i]的时候有两种可能
第一种就是像上面的dp[3]一样，dp[2]求出来是1了，再加上自己array[3]是最大的，
第二种可能就是说如果dp[2]求出来是-100，那如果我也是dp[2]+array[3]的话是-93，
这时候dp[2]反而拖垮了array[3]，最大就是自己
也就是可以退出dp的状态方程 dp[i] = max(dp[i-1]+array[i], array[i]);
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];
    vector<int> dp(n); // 默认用0初始化 
    dp[0] = v[0];
    int ret = 0;
    for(size_t i = 1; i < n; ++i)
    {
        dp[i] = max(dp[i-1] + v[i], v[i]);
    }
    // 找出最大的dp[i]
    sort(dp.begin(), dp.end());
    ret = dp[dp.size()-1];
    cout << ret << endl;
    return 0;
}
// 由于用到了sort 因此时间复杂度变成 O(NlogN)

不要sort的写法，时间复杂度才是真正的O(n)，空间复杂度O(n)

/*
2022年09月10日 12:43:41
dp[i]是以数组下标为 i 的数做为结尾的最大子序列和，注意是以 i 为结尾
比如说现在有一个数组 {6,-3,-2,7,-15,1,2,2}
dp[2]就是以-2为结尾的，那么显然dp[2]的最大值就是1（6，-3，-2），
dp[3]要以7结尾，那么以7结尾的子序列最大和就是8（6，-3，-2，7）。
求dp[i]的时候有两种可能
第一种就是像上面的dp[3]一样，dp[2]求出来是1了，再加上自己array[3]是最大的，
第二种可能就是说如果dp[2]求出来是-100，那如果我也是dp[2]+array[3]的话是-93，
这时候dp[2]反而拖垮了array[3]，最大就是自己
也就是可以退出dp的状态方程 dp[i] = max(dp[i-1]+array[i], array[i]);
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];
    vector<int> dp(n); // 默认用0初始化 
    dp[0] = v[0];
    int maxSum = v[0];
    for(size_t i = 1; i < n; ++i)
    {
        dp[i] = max(dp[i-1] + v[i], v[i]);
        maxSum = max(dp[i], maxSum); // 用maxSum来维护dp中的最大值，这样最终时间复杂度依旧还是O(N)
        // 不过空间复杂度也是O(N)
    }
    cout << maxSum << endl;
    return 0;
}

dp优化

时间复杂度O(n)，空间复杂度O(1)

/*
2022年09月10日 12:43:41
dp[i]是以数组下标为 i 的数做为结尾的最大子序列和，注意是以 i 为结尾
比如说现在有一个数组 {6,-3,-2,7,-15,1,2,2}
dp[2]就是以-2为结尾的，那么显然dp[2]的最大值就是1（6，-3，-2），
dp[3]要以7结尾，那么以7结尾的子序列最大和就是8（6，-3，-2，7）。
求dp[i]的时候有两种可能
第一种就是像上面的dp[3]一样，dp[2]求出来是1了，再加上自己array[3]是最大的，
第二种可能就是说如果dp[2]求出来是-100，那如果我也是dp[2]+array[3]的话是-93，
这时候dp[2]反而拖垮了array[3]，最大就是自己
也就是可以退出dp的状态方程 dp[i] = max(dp[i-1]+array[i], array[i]);
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i)
        cin >> v[i];
    int sum = v[0];
    int maxSum = v[0];
    for(size_t i = 1; i < n; ++i)
    {
        sum = max(sum + v[i], v[i]); // 利用一个sum来充当dp[i] 空间复杂度达到O(1) 不消耗额外空间
        maxSum = max(sum, maxSum);
    }
    cout << maxSum << endl;
    return 0;
}