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)