c++ - 对于给定的n个数字序列，尽可能以最低的计算复杂度找到总和最大的子串

Question

任务:对于给定的n个数字序列，找出总和最大的子串。我用 C++ 创建了我的代码，它给出了正确的答案。我想知道是否有可能以较低的计算复杂度来解决此任务？ 输入示例:

20
8973
-4625
-2038
3405
-7004
-9853
-361
3294
4036
8767
1711
-3100
2139
-4993
-9572
3789
2472
-6170
5408
2200

输出:

17808

我的实际代码:

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

typedef long long int lint;

int main()
{
    lint t = 0;
    cin >> t;
    vector<lint> Ar;
    bool st = false;
    for (lint i = 0; i < t; i++)
    {
        lint n = 0;
        cin >> n;
        if (st == true)Ar.push_back(n);
        else if (n>0 && st == false)
        {
            Ar.push_back(n);
            st = true;
        }

    }
    if (Ar.size() == 0)
    {
        cout << "0" << endl;
    }
    else
    {
        vector<lint> Adding;
        for (std::size_t i = 0; i < Ar.size(); i++)
        {
            if (Ar[i] > 0)
            {
                Adding.push_back(i);
            }
        }



        vector<lint> D;
        for (std::size_t j = 0; j < Adding.size(); j++)
        {
            lint s = 0;

            for (std::size_t i = Adding[j]; i < Ar.size(); i++)
            {


                if (Ar[i] > 0)
                {
                    s += Ar[i];
                    D.push_back(s);
                }
                else
                {
                    s += Ar[i];
                }
            }

        }

        vector<lint>::const_iterator it2;
        // Find max element in the vector
        it2 = max_element(D.begin(), D.end());
        cout << *it2 << endl;
    }
    return 0;
}

Answer 1

解决此任务的最佳计算复杂度是线性的。另一方面，您的代码不是线性的，因此您的问题的答案是 - 是的，可以更复杂地解决问题。

您正在解决的问题称为 Maximum subarray problem并且相当有名。