CODEWITHSUNDEEP
c++arraysdynamic-programming
user2579402
user2579402

Reputation: 23

Maximum array sum with limit

Cant find this question.We are given an array,we have to find maximum sum of consecutive elements but the maximum sum limit is given.For ex- in array 7 3 5 6,and maximum allowed sum is 9,so the answer should be 8 is given.The only thing i find on internet is maximum possible sum,but i want to find the limited sum

#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;
}

Upvotes: 0

Views: 3068

Answers (2)

haykart
haykart

Reputation: 957

I guess you can find full answer to your question here: Algorithm for Filling bag maximally (this is not the knapsack 0/1) This question was created by me, feel free to ask for details :)

Upvotes: 0

songlj
songlj

Reputation: 927

If the numbers in the array are all positive numbers, here is an O(n) algorithm: Use 2 pointers, one pointing to the start position and another pointing to the end position. Move the later pointer ahead, whenever the current sum is larger than the limit, move the first pointer and minus the sum.

Simple code:

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;

If the array contains negative numbers, currently I can only think of an O(n^2) algorithm.

Upvotes: 1

Related Questions