Solution technique of 10684- The jckpot

Problem Description
source: https://uva.onlinejudge.org/external/106/10684.html

Solving Technique:

This is a maximum subarray summation related problem. We have to find the maximum subarray from a one-dimensional array and sum-up all values of sub array then we will get the patterns of consecutive wins that will give maximum benefit and elaborate a win-win strategy.

Using Kadane’s algorithm we can solve in O(n) time.


Kadane’s Algorithm:

Initialize:
    sum = 0
    maxSum = 0

Loop for each element of the array
   sum += array[i]
   if(sum < 0)
     sum = 0
   if(maxSum < sum)
     maxSum = sum
return maxSum

In this algorithm, if the sum of array elements become 0 or negative then we should set the sum to zero. That means we didn’t want to take any previous elements and we will be finding the next sequence. If we keep negative sum then we will never have the correct answer.

Example:

5
12 -4 -10 4 9

In this example sum up from the first element to -10 we got -2 and then if we add 4, 9 to the current sum -2 the max value is 11. But we could get a better result by discarding all previous sums since 12, -4 and -10 produces a negative sum -2. So we discard all previous sums till -10 then adding 4, 9 and we get the max value of 13.