Codility - Lesson 9 Maximum Slice Problem

Source Link:
https://codility.com/programmers/lessons/9-maximum_slice_problem/

Some Notes: 
Let’s define a problem relating to maximum slices. we are looking for two indices p, q such that the total ap + ap+1 + . . . + aq is maximal.  In the picture, the slice with the largest sum is highlighted in gray.


 
 

9.2. Solution with O(n2) time complexity
Notice that the prefix sum allows the sum of any slice to be computed in a constant time. We assume that pref is an array of prefix sums (prefi = a0 + a1 + . . . + ai≠1).

9.2: Maximal slice — O(n2).
1 def quadratic_max_slice(A, pref):
2 n = len(A), result = 0
3 for p in xrange(n):
4 for q in xrange(p, n):
5 sum = pref[q + 1] - pref[p]
6 result = max(result, sum)
7 return result


9.3. Solution with O(n) time complexity
For each position, we compute the largest sum that ends in that position. If we assume that the maximum sum of a slice ending in position i equals max_ending, then the maximum slice ending in position i+1 equals max(0,max_ending+ ai+1). This time, the fastest algorithm is the one with the simplest implementation. 

9.4: Maximal slice — O(n).
1 def golden_max_slice(A):
2 max_ending = max_slice = 0
3 for a in A:
4 max_ending = max(0, max_ending + a)
5 max_slice = max(max_slice, max_ending)
6 return max_slice 

Notes:

notes are incorrect... we have to use Kadane's Algorithm.
not using "Math.max( 0, maxEndingHere + A[i])"
Instead, using "Math.max( A[i], maxEndingPrevious + A[i] )"