Welcome to FutureAppLaboratory

v=（*＾ワ＾*）=v

Codility - Aluminium 2014 - Part 1

| Comments

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 ,

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

    public int solution(int[] inputs) {
        List<Integer>data = new ArrayList<Integer>();
        for (int i = 0; i < inputs.length; i++) data.add(inputs[i]);
        return cal(data);
    }

    private int cal(List<Integer> A) {
        int n = A.size();
        int S = 0;
        for (Integer integer : A) S += integer;
        List<Integer> B = partial_sum(A, compAdd);
        List<Integer> F = partial_sum(B, compMin);

        Collections.reverse(A);
        List<Integer> D = partial_sum(A, compAdd);
        List<Integer> G = partial_sum(D, compMin);
        Collections.reverse(A);
        Collections.reverse(G);

        int res = 0;
        for (int i = 0; i < n; i++) {
            int f = i - 1 < 0 ? 0 : F.get(i - 1);
            int g = (i + 1 >= n ? 0 : G.get(i + 1));
            res = Math.max(res, S - (f < 0 ? f : 0) - (g < 0 ? g :0));
        }
        return res;
    }

    private List<Integer> partial_sum(List<Integer> data, Comparator<Integer> comparator) {
        List<Integer> res = new ArrayList<Integer>();
        if (data.size() == 0) {
            return res;
        }
        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