0

找不到这个问题。给定一个数组，我们必须找到连续元素的最大和，但给出了最大和限制。例如，在数组 7 3 5 6 中，最大允许和为 9，所以答案应该是给出了 8。我在互联网上找到的唯一东西是最大可能的总和，但我想找到有限的总和

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

int main() 
{
    int n,m,a[100],dp[100];
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum=0;
    for(int i=0;i<n&&sum<=m;i++) 
    {
        int j=0;
        sum=sum+a[i];
        if(sum>m)
        {
            dp[j]=sum-a[i];
        }
        else dp[j]=sum;
        j++;
        sum=0;
    }
    sort(dp,dp+n);
    cout<<dp[n-2];
    return 0;
}
4

2 回答 2

1

如果数组中的数字都是正数，这里是一个 O(n) 算法：使用 2 个指针，一个指向开始位置，另一个指向结束位置。将后一个指针向前移动，每当当前总和大于限制时，移动第一个指针并减去总和。

简单代码：

int sum=0,ans=0,p1=0,p2=0;
while (p2<n) {
    sum+=num[p2];
    p2++;
    while (sum>limit && p1<p2) {
        sum-=num[p1];
        p1++;
    }
    ans=max(ans,sum);
}
while (p1<n) {
    sum-=num[p1];
    p1++;
    if (sum<=limit) ans=max(ans,sum);
}
return ans;

如果数组包含负数，目前我只能想到一个 O(n^2) 算法。

于 2013-10-29T06:28:43.327 回答
0

我想你可以在这里找到你问题的完整答案： 最大填充袋的算法（这不是背包 0/1） 这个问题是我创建的，请随时询问详细信息 :)

于 2017-02-15T13:45:46.540 回答