# Codility - Aluminium 2014 - Part 1

## Introduction

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

• The problem is, finding the maximum sum of a compact subsequence of array elements after performing a single swap operation. It’s a little tricky maximal subarray problem.
• For example, given an array {3, -10, 4, 5}, we can swap 3 and -10 to get a compact subsequence {3, 4, 5}, which has the maximum sum 12
• Time bound and space bound are both O(n)
• There exists many algorithms to solve maximal subarray problems, but they cannot directly applied to this problem.

## Analysis

• First, we will take a look at the solution of a CLASSIC maximal subarray problem, which means swap is not allowed.

For a given array $a_0, a_1, \cdots, a_n-1$,

The maximum sum of a compact subsequence can be expressed by the following formula.

Beca\$use we want the maximal part from $i$ to $j$, by thinking reversely, we can calculate the minimal partial sum of sub array $a_0, a_1, \cdots, a_x-1$ as $f(x)$, minimal partial sum of sub array $a_x+1, a_x+2, \cdots, a_n-1$ as $g(x)$. Then use the whole sum to subtract them if them are minus values.

let $S$ to be the accumulation of the given array.

let

to be the minimal partial sum of sub array $a_0, a_1, \cdots, a_x-1$.

let

to be the minimal partial sum of sub array $a_x+1, a_x+2, \cdots, a_n-w$.

Then we calculate the following formula.

• OK, then write above thought into Java, we get the following codes