UVA Problem 10684 – The jackpot Solution

UVA Problem 10684 – The jackpot Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This is an maximum sub array sum problem. Here we need find maximum subarray sum in 1D array. It can be solved easily with Kadane’s algorithm in O(n) time.

One thing to keep in mind the sample input isn’t properly aligned. So input format may be a bit confusing.

Explanation:

If the sum of array elements become 0 then we should set the sum to zero. Meaning we didn’t take any previous elements. Otherwise if we keep sum negative then we’ll never have the correct answer. Since we could get a bigger sum by discarding negative sum subset.

For example,

5
12  -4  -10  4  9

Here from first element to -10 we have a sum of -2. If we then add 4, 9 to the current sum -2 the max value is 11. But we could get a better result by discarding all previous sum since 12, -4, -10 produces a negative sum. There is no meaning taking a negative value. So discarding all previous sums till -10 then adding 4, 9 we get a max value of 13.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

5
12  -4  -10  4  9
3
-2 -1 -2
0

 


Output:

The maximum winning streak is 13.
Losing streak.

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10684 - The jackpot
 */

#include<stdio.h>

static int subset[10002];

int main(){
	static unsigned n, i;
	static int sum, max;

	while(scanf("%u", &n) && n){

        sum = max = i = 0;

        for(; i < n; ++i){
            scanf("%d", &subset[i]);
            sum += subset[i];

            if(sum < 0)
                sum = 0;

            if(sum > max)
                max = sum;
        }

        if(max > 0)
            printf("The maximum winning streak is %d.\n", max);
        else
            printf("Losing streak.\n");
	}
	return 0;
}
Advertisements