fork download
  1. import java.util.Arrays;
  2.  
  3. class Main {
  4. public static void main (String[] args) {
  5. int[][] testArrays = {
  6. {1, 4, 3, 2, 6, 5},
  7. {2, 5, 3, 7, 8, 1}
  8. };
  9. for (int[] array: testArrays) {
  10. int sum = maxSum(array, 2);
  11. System.out.println(Arrays.toString(array) + " -> " + sum);
  12. }
  13. }
  14.  
  15. /**
  16.   * Find maximum sum of elements in the input array, with at most n adjacent
  17.   * elements included in the sum.
  18.   */
  19. public static int maxSum (int input[], int n) {
  20. int sums[] = new int[n+1]; // new int[] fills the array with zeros
  21. int max = 0;
  22.  
  23. for (int x: input) {
  24. int newMax = max;
  25. // update sums[k] for k > 0 by adding x to the old sums[k-1]
  26. // (loop from top down to avoid overwriting sums[k-1] too soon)
  27. for (int k = n; k > 0; k--) {
  28. sums[k] = sums[k-1] + x;
  29. if (sums[k] > newMax) newMax = sums[k];
  30. }
  31. sums[0] = max; // update sums[0] to best sum possible if x is excluded
  32. max = newMax; // update maximum sum possible so far
  33. }
  34. return max;
  35. }
  36. }
  37.  
Success #stdin #stdout 0.07s 380160KB
stdin
Standard input is empty
stdout
[1, 4, 3, 2, 6, 5] -> 18
[2, 5, 3, 7, 8, 1] -> 22