任意长度的两个非重叠子阵列的最大和

Question

我从leet code https://leet code . com/problems/Maximum-Sum-of-Two-Non-Overlapping-Subarrays/中看到“两个非重叠子数组的最大和(特定给定长度，数组只包含正数)”。

但我遇到了这个问题的一个变体——“两个非重叠子数组（任意长度）的最大和，并且该数组包含正数和负数”。我看不到任何编码平台有这个问题需要我确认我的解决方案。

我的理论解决方案：

>

创建一个名为“maxSumAtIndex”的新数组，并在每个索引处插入最大可能的总和。即如果前一个索引的值加上当前索引的值大于当前索引的值，则将该值插入当前索引中，或者仅插入当前索引的值。（

在数组“最大总和索引”（例如索引 10）中查找最大值的索引。从该索引回遍历（朝向索引 0），并得到第二高值的索引（比如索引 7）。原始数组中这 2 个索引（7 和 10）之间的值之和将给出其中一个子数组的总和。

另一个子数组位于0-6或11-20之间。在数组“maxSumAtIndex”（例如索引18）中查找这两个子数组中的最大值。从该索引（18）向后遍历到索引11，并找到11-20之间第二高值的索引（例如索引12）。原始数组中这两个索引（12和18）之间的值之和将给出第二个子数组的和。

finalSum = 步骤 （2） 的总和步骤 （3） 的总和

问题：

>

如果有任何平台有这个问题，我想知道。

我针对几个自制的测试用例运行了上述解决方案，它似乎有效。虽然我可以看到一种模式，这可能有效，但我无法弄清楚它为什么有效（就像外行证明一样）。这个解决方案是否正确，如果是正确的，为什么它有效？

-9 5 -9 -8 [9 7] -10 [10 9] = 35

-9 5 -4 -8 9 16 6 16 25

指数8最高25。索引7处的第二高16(第一次出现)。将原始数组的索引7到索引8相加-

最高 16 在索引 5.指数4位居第二，排名第二。将原始数组的索引 4 求和到索引 5 -

19 16 = 35

Answer 1

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

//for the case when subarray size can be zero 

int maxSubArraySum(vector<int> arr, int start, int end)
{
    int max_so_far = arr[start], curr_max = arr[start];

    for (int i = start + 1; i < end; i++)
    {
        curr_max = max(arr[i], curr_max + arr[i]);
        max_so_far = max(max_so_far, curr_max);
    }
    return max_so_far > 0 ? max_so_far : 0;
}
int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n, i++)
    {
        cin >> arr[i];
    }
    int ans = 0;
    for(int i=0; i<n, i++)
    {
        int a = maxSubArraySum(arr, 0, i);
        int b = maxSubArraySum(arr, i, n);
        ans = max(ans, a + b);
    }
    cout << ans;
    return 0;
}

Answer 2

#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin>>n;
    vector<int>nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    vector<int>aagesekadane; //aagesekadane <=>kadaneFromFront 
    vector<int>pichesekadane(n);  //pichesekadane <=>kadaneFromBack
    int cs=0;
    int ca=0;
    aagesekadane.push_back(0);
    pichesekadane.push_back(0);
    for(int i=0;i<nums.size();i++){
        cs+=nums[i];
        if(cs>ca){
            ca=cs;
        }
        if(cs<0)cs=0;
        aagesekadane.push_back(ca);
    }
    cs=0;
    ca=0;
    for(int i=nums.size()-1;i>=0;i--){
        cs+=nums[i];
        if(cs>ca){
            ca=cs;
        }
        if(cs<0)cs=0;
        pichesekadane[i]=ca;
    }
    
    int ans=0;
    for(int i=0;i<=n;i++){
            ans=max(ans,aagesekadane[i]+pichesekadane[i]);
        
    }
cout<<ans<<endl;
}
int main() {
    int t;
    cin>>t;
    while(t--){
    solve();
    }
    return 0;
}

希望这能奏效

Answer 3

我看不出有任何理由相信你的算法有效，但是一个简单的算法是运行Kadane的算法在每个位置之前找到最大和子数组，然后反向运行Kadane的算法以在每个位置之后找到最大的和子数组。

由于不相交的子阵列必须在某个位置的任一侧，因此只需检查所有位置，以找到前后最大和阵列的最大和。