find longest subsequence with sum less than or equal to k

Question

I have a vector<int> num, I want to get the size of longest subarray with the sum less than or equal to k.

My approach: O(n^2). Repeat for every element in the array.

Can we do better?'

Note: I don't need the actual longest subarray, only its size. So the return value is int.

• candied_orange: Can the elements be negative?

Answer 1

Assuming, that the vector contains only non-negative integers:

int getLargestSubsequenceSize(vector<int>& myVector, int k){
 int maxCount = 0;
 int i=0,j=0;
 int sum = 0;
 while(j < myVector.size()){
 sum += myVector[j];
 if(sum > k){
 int currCount = j-i;
 if(currCount > maxCount)
 maxCount = currCount;
 sum -= myVector[i];
 i++;
 } 
 j++;
 }
 return maxCount;
}

The above function has two indexes (i,j). j will increment and add current number to the sum until sum becomes greater than k. Once it is greater, we will calculate the length of this sub-sequence and check whether it is bigger than previous subsequence. If yes, we will update the maxCount. Now, we will increment the lower index (i) and repeat the process. Time Complexity = O(n)

• Robert Harvey: Explain how this works, and why it's better than O(n^2)