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 ,

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

Beca$use we want the maximal part from to , by thinking reversely, we can calculate the minimal partial sum of sub array as , minimal partial sum of sub array as . Then use the whole sum to subtract them if them are minus values.

let to be the accumulation of the given array.

let

to be the minimal partial sum of sub array .

let

to be the minimal partial sum of sub array .

Then we calculate the following formula.

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