import java.util.Arrays;
 
class Main {
    public static void main (String[] args) {
        int[][] testArrays = {
            {1, 4, 3, 2, 6, 5},
            {2, 5, 3, 7, 8, 1}
        };
        for (int[] array: testArrays) {
            int sum = maxSum(array, 2);
            System.out.println(Arrays.toString(array) + " -> " + sum);
        }
    }
 
    /**
     * Find maximum sum of elements in the input array, with at most n adjacent
     * elements included in the sum.
     */
    public static int maxSum (int input[], int n) {
        int sums[] = new int[n+1];  // new int[] fills the array with zeros
        int max = 0;
 
        for (int x: input) {
            int newMax = max;
            // update sums[k] for k > 0 by adding x to the old sums[k-1]
            // (loop from top down to avoid overwriting sums[k-1] too soon)
            for (int k = n; k > 0; k--) {
                sums[k] = sums[k-1] + x;
                if (sums[k] > newMax) newMax = sums[k];
            }
            sums[0] = max;  // update sums[0] to best sum possible if x is excluded
            max = newMax;   // update maximum sum possible so far
        }
        return max;
    }
}
 

aW1wb3J0IGphdmEudXRpbC5BcnJheXM7CgpjbGFzcyBNYWluIHsKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgaW50W11bXSB0ZXN0QXJyYXlzID0gewogICAgICAgICAgICB7MSwgNCwgMywgMiwgNiwgNX0sCiAgICAgICAgICAgIHsyLCA1LCAzLCA3LCA4LCAxfQogICAgICAgIH07CiAgICAgICAgZm9yIChpbnRbXSBhcnJheTogdGVzdEFycmF5cykgewogICAgICAgICAgICBpbnQgc3VtID0gbWF4U3VtKGFycmF5LCAyKTsKICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKEFycmF5cy50b1N0cmluZyhhcnJheSkgKyAiIC0+ICIgKyBzdW0pOwogICAgICAgIH0KICAgIH0KCiAgICAvKioKICAgICAqIEZpbmQgbWF4aW11bSBzdW0gb2YgZWxlbWVudHMgaW4gdGhlIGlucHV0IGFycmF5LCB3aXRoIGF0IG1vc3QgbiBhZGphY2VudAogICAgICogZWxlbWVudHMgaW5jbHVkZWQgaW4gdGhlIHN1bS4KICAgICAqLwogICAgcHVibGljIHN0YXRpYyBpbnQgbWF4U3VtIChpbnQgaW5wdXRbXSwgaW50IG4pIHsKICAgICAgICBpbnQgc3Vtc1tdID0gbmV3IGludFtuKzFdOyAgLy8gbmV3IGludFtdIGZpbGxzIHRoZSBhcnJheSB3aXRoIHplcm9zCiAgICAgICAgaW50IG1heCA9IDA7CgogICAgICAgIGZvciAoaW50IHg6IGlucHV0KSB7CiAgICAgICAgICAgIGludCBuZXdNYXggPSBtYXg7CiAgICAgICAgICAgIC8vIHVwZGF0ZSBzdW1zW2tdIGZvciBrID4gMCBieSBhZGRpbmcgeCB0byB0aGUgb2xkIHN1bXNbay0xXQogICAgICAgICAgICAvLyAobG9vcCBmcm9tIHRvcCBkb3duIHRvIGF2b2lkIG92ZXJ3cml0aW5nIHN1bXNbay0xXSB0b28gc29vbikKICAgICAgICAgICAgZm9yIChpbnQgayA9IG47IGsgPiAwOyBrLS0pIHsKICAgICAgICAgICAgICAgIHN1bXNba10gPSBzdW1zW2stMV0gKyB4OwogICAgICAgICAgICAgICAgaWYgKHN1bXNba10gPiBuZXdNYXgpIG5ld01heCA9IHN1bXNba107CiAgICAgICAgICAgIH0KICAgICAgICAgICAgc3Vtc1swXSA9IG1heDsgIC8vIHVwZGF0ZSBzdW1zWzBdIHRvIGJlc3Qgc3VtIHBvc3NpYmxlIGlmIHggaXMgZXhjbHVkZWQKICAgICAgICAgICAgbWF4ID0gbmV3TWF4OyAgIC8vIHVwZGF0ZSBtYXhpbXVtIHN1bSBwb3NzaWJsZSBzbyBmYXIKICAgICAgICB9CiAgICAgICAgcmV0dXJuIG1heDsKICAgIH0KfQo=