Given an array of integers A and an integer k, find a subarray that contains the largest sum, subject to a constraint that the sum is less than k?

https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-contains-the-largest-sum-subject-to-a-constraint-that-the-sum-is-less-than-k

I meant contiguous elements in the array. Also, elements can be positive and negative.

You can do this in O(nlog(n))$O(n\log (n))$

First thing to note is that sum of subarray (i,j]$(i,j]$ is just the sum of the first j$j$ elements less the sum of the first i$i$ elements. Store these cumulative sums in the array cum. Then the problem reduces to finding  i,j$i,j$ such that i<j$i<j$ and cum[j]−cum[i]$cum[j]-cum[i]$ is as close to k$k$ but lower than it.

To solve this, scan from left to right. Put the cum[i]$cum[i]$ values that you have encountered till now into a set. When you are processing cum[j]$cum[j]$ what you need to retrieve from the set is the smallest number in the set such which is bigger than cum[j]−k$cum[j]-k$. This lookup can be done in O(logn)$O(\log n)$ using upper_bound. Hence the overall complexity is O(nlog(n))

1. int best_cumulative_sum(int ar[],int N,int K)
2. {
3. set<int> cumset;
4. cumset.insert(0);
6. int best=0,cum=0;
8. for(int i=0;i<N;i++)
9. {
10. cum+=ar[i];
11. set<int>::iterator sit=cumset.upper_bound(cum-K);
12. if(sit!=cumset.end())best=max(best,cum-*sit);
13. cumset.insert(cum);
14. }
16. return best;
17. }

https://gist.github.com/ducalpha/0075af5cd06e4f81b762