## Thursday, June 23, 2016

### 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\left(n\mathrm{log}\left(n\right)\right)$

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

To solve this, scan from left to right. Put the $cum\left[i\right]$ values that you have encountered till now into a set. When you are processing $cum\left[j\right]$ what you need to retrieve from the set is the smallest number in the set such which is bigger than $cum\left[j\right]-k$. This lookup can be done in $O\left(\mathrm{log}n\right)$ using upper_bound. Hence the overall complexity is
1. int best_cumulative_sum(int ar[],int N,int K)
2. {
3.  set<int> cumset;
4.  cumset.insert(0);
5.  int best=0,cum=0;
6.  for(int i=0;i<N;i++)
7.  {
8.  cum+=ar[i];
9.  set<int>::iterator sit=cumset.upper_bound(cum-K);
10.  if(sit!=cumset.end())best=max(best,cum-*sit);
11.  cumset.insert(cum);
12.  }
13.  return best;
14. }