# 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
The text passage describes a problem from the Codility - Aluminium 2014 Challenge, Part 1, which involves finding the maximum sum of a compact subsequence of array elements after a single swap operation. It includes a detailed analysis and a mathematical approach to solving the problem, but does not contain a direct mathematical question or an answer to such a question.
no_question
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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
user
The text passage describes a problem from the Codility - Aluminium 2014 Challenge, Part 1, which involves finding the maximum sum of a compact subsequence of array elements after a single swap operation. It includes a detailed analysis and a mathematical approach to solving the problem, but does not contain a direct mathematical question or an answer to such a question.

TYPE: NO_QUESTION