# Codility Max Double Slice Sum

#### Posted on January 2, 2014

##### Last updated on January 2, 2014

Solution to Codility Max Double Slice Sum problem.

We can use Kadane’s algorithm from two directions. First, we can safely ignore A[0] and A[N-1] since by definition they can’t be a part of any double-slice sum.

Now, define K1[i] as the maximum sum contiguous subsequence ending at index $$i$$, and similarly, define K2[i] as the maximum sum contiguous subsequence starting with index $$i$$.

Then, iterate over $$i$$, and find the maximum sum of K1[i-1]+K2[i+1]. This is the max double slice sum.

The 100/100 Java code:

Markdown SHA1: 10c16ae8b721bb1e5f5bf7f17b556a1bfe020a61