4
  • 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.

2

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.

1

I know it's late, but here I go,

My solution is recursive, with two options at each function call,

  • If the array already satisfies the condition t, return it's length
  • else there are two options for generating a subsequence, either remove an element from the beginning or remove and element from the end. So, you invoke the exact same function recursively for both the options the return the maximum length of the two.

    def search_subs(a, k):
       #print "array is: ", a
       if sum(a) <= k:
           return a.__len__()
       else:
           return max(search_subs(a[1:], k), search_subs(a[:-1], k))
    
    print search_subs([2,2,3], 3)
    

Worst case complexity is O(n ln n), I believe.

0

Instead of asking "why does the last approach work", you should ask "does the last approach work". It doesn't. start is increased by 1 exactly once in each iteration of the loop, and curr_sum will be equal to 0 after start is increased. This will never find a solution unless sum == 0.

I strongly suspect that there should be some "while" statement before the code that subtracts array [start] and increases start.

  • 1
    Forgot a line sorry. Actually solution 1 is the right solution and solution is a similar solution to similar question – RE60K May 30 '16 at 19:40
  • 1
    See edit to the question – RE60K May 30 '16 at 19:42

protected by gnat Aug 16 '17 at 9:07

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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