0

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.

  • Can the elements be negative? – candied_orange Oct 23 '16 at 3:11
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)

  • 2
    Explain how this works, and why it's better than O(n^2) – Robert Harvey Oct 23 '16 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.