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 つのポインターを使用します。1 つは開始位置を指し、もう 1 つは終了位置を指します。現在の合計が制限よりも大きい場合は常に、後のポインターを前方に移動し、最初のポインターを移動して合計を差し引きます。

簡単なコード:

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 に答える