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.

Improve this question
4
  • 1
    Should a question that is meaningless without viewing an external link be closed? Commented May 30, 2016 at 13:28
  • I was about to post the same thing as gnat actually. @ADG, keep in mind that the "closed" status is not a dead-end. Its purpose is to allow the asker to fix up their question and get it re-opened. There is no need to rush :) Commented May 30, 2016 at 13:40
  • @gnat how is the edit? what should i do now? Commented May 30, 2016 at 13:40
  • 1
    very nice edit btw. Commented May 30, 2016 at 13:41

3 Answers 3

Reset to default
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.

Improve this answer
0
2

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.

Improve this answer
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.

Improve this answer
2
  • 1
    Forgot a line sorry. Actually solution 1 is the right solution and solution is a similar solution to similar question Commented May 30, 2016 at 19:40
  • 1
    See edit to the question Commented May 30, 2016 at 19:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.