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);
}
}
/**
* 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=
[1, 4, 3, 2, 6, 5] -> 18
[2, 5, 3, 7, 8, 1] -> 22