# Codility - Aluminium 2014 - Part 2

## Introduction

This is an analysis of Codility - Aluminium 2014 Challenge, Part 2.

In Part 1, we introduced a solution for CLASSIC maximal subarray problem.
Now we’ll make a solution for the swap version.

## Analysis

We want to use the strategy described in Part 1.

### 1. Split input array

We split given array $a_0, a_1, \cdots, a_n-1$ by index $i$. Then we get subarray $L_1 = {a_0, a_1, \cdots, a_i}$ and $L_2 = {a_i+1, a_i+2, \cdots, a_n-1}$.

### 2. Limited Swap

Note that, we consider that a swap of $a_j$ and $a_k$ only occurs in array $L_1$, $0 \leq j < k < i$. Why? If such a swap occurs in $L_2$, we just reverse the input array, then do the same calculation on it again to get the result.

Now we want to minimize partial sum of $L_1$(after a swap) and $L_2$, as we did in Part 1.

### 3. Calculation on $L_1$(after a swap)

The principle is, for each $a_k$, we should swap $a_k$ with $a_j$, which is the greatest member in $a_0, a_1, \cdots, a_k-1$. We can do this step by step.

● Calculate partial sum of $L_1$, stored in $psum$ array.

● Calculate the greatest member’s value in $a_0, a_1, \cdots, a_x$

● We define $minsub(x)$ as the possible minimal partial sum we could get for $a_0, a_1, \cdots, a_x$, by remove(swap out) the greatest member.

● Last, we define $L_1(x)$ as the possible minimal partial sum after swap in $a_x$. Note that for $x=0$, there is only one element in partial array $a_0$, so we cannot make a swap. We just store $a_0$’s value as minimal partial sum.

### Calculation on $L_2$

Calculation on $L_2$ is the same as we described in Part 1.

### Merge

Use results of $L_1$ and $L_2$. The largest one is the answer.

Because calculation above is on 1-d array, time and space complexity are O(n).

Code