Maximum array sum with limit

Question

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

tried to come up with some sort of this algo /*#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; }*/ — user2579402
– user2579402, Commented Oct 28, 2013 at 7:08

songlj · Accepted Answer · 2013-10-29 06:28:43Z

1

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.

answered Oct 29, 2013 at 6:28

songlj

9371 gold badge6 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Community · Accepted Answer · 2017-05-23 12:34:06Z

0

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 :)

edited May 23, 2017 at 12:34

CommunityBot

11 silver badge

answered Feb 15, 2017 at 13:45

haykart

9775 gold badges14 silver badges37 bronze badges

Collectives™ on Stack Overflow

Maximum array sum with limit

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related