Algorithms – Finding Longest Subsequence with Sum Less Than or Equal to a Fixed Number

algorithmsbig o

  • I was trying to solve Problem 279-B.

    Given an natural number, t, and an array, a[0],...,a[n-1], of natural numbers, find the maximum length of a continuous subarray, a[i],...,a[j] in a where a[i]+...+a[j] <= t. e.g. a=[3,1,2,1] and t=5 -> 3(1,2,1) ; a=[2,2,3] and t=3 -> 1

  • I thought of an O(n2) solution.

    Double looping to calculate sums and kind of brute force.

  • I also thought of maximum sum of a subarray in an array by dynamic programming.
  • I saw this solution which is O(n lg n)

By creating a sum array defined as:

sum[i]=sum[i−1]+array[i]//  for  all   i>0.
sum[i]=array[i]    // for   i=0

Then finding j such that (by binary search)

sum[j]−sum[i]//j>i

Solution 1:

    int n; long t; scanf("%d %ld", &n, &t);
    long *minutes = new long[n];
    long totalTime = 0;
    for(int k = 0; k < n; k++){scanf("%ld", minutes + k); totalTime += minutes[k];}

    long start(0), finish(0), currentSum(0), output(0);

    while(finish < n){
        currentSum += minutes[finish++];
        while(currentSum > t){currentSum -= minutes[start++];}
        if(output < finish - start){output = finish - start;}
    }

    printf("%ld\n", output);

    delete[] minutes;
    return 0;

Solution 2:

    int curr_sum = arr[0], start = 0, i;

    for (i = 1; i <= n; i++)
    {
    // If curr_sum exceeds the sum, then remove the starting elements
       while (curr_sum > sum && start < i-1)
       {
            curr_sum = curr_sum - arr[start];
            start++;
        }
        if (curr_sum == sum)
        {
            printf ("Sum found between indexes %d and %d", start, i-1);
            return 1;
        }
        if (i < n)
          curr_sum = curr_sum + arr[i];
    }
    printf("No subarray found");
    return 0;

Why does the last approach work(Solution 1for sum less than a fixed number and solution 2 for sum equal to a fixed number) I don't seem to get it. I couldn't find the reason or proof for it. I don't know whether it's a named algorithm.

Best Answer

Now you've fixed the post, it is rarely a good idea trying to understand an algorithm from the implementation. It is much easier to develop the algorithm and the code.

Let's start with a simple thing: Given a start position in an array, how many array elements can we add from the starting position so that the sum is not greater than t? That is, given an index 'start', find an index 'end' ≤ n, so that array [start] + array [start + 1] + ... + array [end - 1] ≤ t, and either end = n or adding array [end] would make the sum > t.

That's quite simple. Given start, we write

end = start; 
sum = 0; 
while (end < n && sum + array [end] <= t) {
    sum += array [end];
    end += 1;
}

Simple, but it can be slow. Say we have n = 1,000,000, t = 1,000,000 and all the array elements are 1 or 2, we will always add up at least half a million values, and that for a million possible values of start.

When we check the next value start+1, we know that the sum of array elements from array [start] to array [end - 1] is ≤ t, therefore since array [start] ≥ 0 we also know that the sum array [start+1] to array [end - 1] is ≤ t. And we calculate that sum in one operation by subtracting array [start] from the current sum. So to calculate "end" for each of the values of start, we use this code: 

end = 0;
sum = 0;
for (start = 0; start < n; ++start) {
    while (end < n && sum + array [end] <= t) {
        sum += array [end];
        end += 1;
    }
    /* Do something with start, end, sum */
    sum -= array [start];
}

When start = 0, we do the same thing as in the first version. For larger n, we start the inner loop with a value for end that isn't too large, and the sum up to that point correctly added up. Obviously you can now easily do things like finding the largest sum, finding the sum with the largest or smallest number of elements and so on.

The execution time is O (n), because both start and end are increased by 1 exactly n times.

Related Topic