Welcome to FutureAppLaboratory

v=（*＾ワ＾*）=v

Codility - Aluminium 2014 - Part 2

| Comments

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 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).

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

public int solution(int[] inputs) {

    List<Integer>data = new ArrayList<Integer>();
    List<Integer> rdata = new ArrayList<Integer>();
    for (int i = 0; i < inputs.length; i++) data.add(inputs[i]);
    for (int i = 0; i < inputs.length; i++) rdata.add(inputs[inputs.length - 1 - i]);

    int r1 = cal(data);
    int r2 = cal(rdata);

    int result = 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) {
        return Collections.max(data);
    } else {
        return result;
    }
}

private int cal(List<Integer> data) {
    int n = data.size();
    int sum = 0;
    for (Integer integer : data) sum += integer;

    List<Integer> psum = partial_sum(data, compAdd);
    List<Integer> pmax = partial_sum(data, compMax);
    List<Integer> sub = new ArrayList<Integer>();
    for (int i = 0; i < n; i++) {
        sub.add(psum.get(i) - pmax.get(i));
    }

    List<Integer> min_sub = partial_sum(sub, compMin);
    List<Integer> L1 = new ArrayList<Integer>();
    for (int i = 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.
    int best = 0;
    for (int i = 0; i < n; i++) {
        best = Math.max(best, sum - L1.get(i) - (i + 1 >= n ? 0 : L2.get(i+1)) );
    }
    return best;
}

private List<Integer> partial_sum(List<Integer> data, Comparator<Integer> comparator) {
    List<Integer> res = new ArrayList<Integer>();
    if (data.size() == 0) {
        return null;
    }
    res.add(data.get(0));
    for (int i = 1; i < data.size(); i++) {
        Integer lastValue = res.get(i - 1);
        Integer currentValue = data.get(i);
        res.add(comparator.compare(lastValue, currentValue));
    }
    return res;
}

Comparator<Integer> compAdd = new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 + o2;
    }
};

Comparator<Integer> compMax = new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return Math.max(o1, o2);
    }
};

Comparator<Integer> compMin = new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return Math.min(o1, o2);
    }
};

Comments