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.


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,

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.


12  -4  -10  4  9
-2 -1 -2



The maximum winning streak is 13.
Losing streak.


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


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);
            printf("Losing streak.\n");
	return 0;

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s