We split given array by index . Then we get subarray and .

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 (after a swap) and , 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 and . The largest one is the answer.

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

publicintsolution(int[]inputs){List<Integer>data=newArrayList<Integer>();List<Integer>rdata=newArrayList<Integer>();for(inti=0;i<inputs.length;i++)data.add(inputs[i]);for(inti=0;i<inputs.length;i++)rdata.add(inputs[inputs.length-1-i]);intr1=cal(data);intr2=cal(rdata);intresult=Math.max(r1,r2);// result equals 0 means no subarray have sum larger than 0,// we need to choose a largest negative element.if(result==0){returnCollections.max(data);}else{returnresult;}}privateintcal(List<Integer>data){intn=data.size();intsum=0;for(Integerinteger:data)sum+=integer;List<Integer>psum=partial_sum(data,compAdd);List<Integer>pmax=partial_sum(data,compMax);List<Integer>sub=newArrayList<Integer>();for(inti=0;i<n;i++){sub.add(psum.get(i)-pmax.get(i));}List<Integer>min_sub=partial_sum(sub,compMin);List<Integer>L1=newArrayList<Integer>();for(inti=0;i<n;i++){L1.add(Math.min((i-1>=0?min_sub.get(i-1):0)+data.get(i),(i-1>=0?L1.get(i-1):0)));}Collections.reverse(data);List<Integer>r_psum=partial_sum(data,compAdd);List<Integer>L2=partial_sum(r_psum,compMin);Collections.reverse(L2);// We can split array into L1 and L2 at index i form 0 to n - 1. We just take the largest.intbest=0;for(inti=0;i<n;i++){best=Math.max(best,sum-L1.get(i)-(i+1>=n?0:L2.get(i+1)));}returnbest;}privateList<Integer>partial_sum(List<Integer>data,Comparator<Integer>comparator){List<Integer>res=newArrayList<Integer>();if(data.size()==0){returnnull;}res.add(data.get(0));for(inti=1;i<data.size();i++){IntegerlastValue=res.get(i-1);IntegercurrentValue=data.get(i);res.add(comparator.compare(lastValue,currentValue));}returnres;}Comparator<Integer>compAdd=newComparator<Integer>(){@Overridepublicintcompare(Integero1,Integero2){returno1+o2;}};Comparator<Integer>compMax=newComparator<Integer>(){@Overridepublicintcompare(Integero1,Integero2){returnMath.max(o1,o2);}};Comparator<Integer>compMin=newComparator<Integer>(){@Overridepublicintcompare(Integero1,Integero2){returnMath.min(o1,o2);}};