最大數組總數與極限

Question

不能找到這個問題。我們給出一個數組，我們必須找到連續元素的最大總和，但是給出了最大總數限制。對於數組7 3 5 6中的ex-in和最大允許和是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; 
} 

Answer 1

如果數組中的數字都是正數，這裏是一個O（n）算法：使用2個指針，一個指向開始位置，另一個指向結束位置。每當當前總和大於限制時，將較晚的指針向前移動，移動第一個指針並減去總和。

Simple代碼：

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）的算法。

Answer 2

經典最大總和的問題是通過以下邏輯求解動態規劃：

• 讓S[i]是在陣列的索引i結束最大總和。
• 設array是你的長度的陣列n含正或負的值
• 我們知道，S[0] = array[0]，因爲沒有其他值是索引之前存在於陣列中0
• S[i] = max(S[i-1] + array[i], array[i])也就是說，最大值在指數可達我是將數組[i]添加到前一個最大值，或者只是數組[i]。如果以前的最大值爲負數或0，那麼我們總是想要數組[i]，而這個邏輯就是這樣的：

動態編程解決方案具有O（n）複雜性。

您的問題稍有不同。你對S [i]有一個上限。這個上限顯着改變了問題的複雜性，因爲現在我們可能需要積累負數以便達到最大限制。即，對於輸入：

-1 -2 6，LIMIT = 3

我們將要發現的，我們的確可以達到我們的極限。

我們可以在O解決這個問題（N ）時間通過考慮從開始array[i]，這是O（n）的時間對於每個索引的所有可能的連續的序列。這不是很動態的編程，但我認爲這是我們可以獲得的最高效率。

Answer 3

我想你可以找到完整的答案在這裏你的問題： Algorithm for Filling bag maximally (this is not the knapsack 0/1) 這個問題是由我創建，隨意詢問詳情:)