import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class MaxArraySum {

  private static final String SPACE = " ";

  private static int[] readNumbers() throws IOException {
    try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
      reader.readLine(); // Skip array length line.
      String[] split = reader.readLine().split(SPACE);
      return Arrays.stream(split).mapToInt(Integer::parseInt).toArray();
    }
  }

  private static List<Integer> findNextIndices(int currentIndex, int[] numbers) {
    List<Integer> nextIndices = new ArrayList<>();
    for (int i = currentIndex + 2; i < numbers.length; i++) {
      if (numbers[i] > 0) {
        nextIndices.add(i);
        int next = i + 1;
        if (next < numbers.length && numbers[next] > 0) {
          nextIndices.add(next);
        }
        return nextIndices;
      }
    }
    return nextIndices;
  }

  private static void addToCache(Map<Integer, List<Long>> cache,
      int key, long value) {
    List<Long> cachedResults = cache.getOrDefault(key, new ArrayList<>());
    if (!cachedResults.contains(value)) {
      cachedResults.add(value);
      cache.put(key, cachedResults);
    }
  }

  private static long getMaxValue(Map<Integer, List<Long>> cache) {
    long maxValue = 0;
    for (List<Long> cachedValues : cache.values()) {
      for (long value : cachedValues) {
        maxValue = (value > maxValue) ? value : maxValue;
      }
    }
    return maxValue;
  }

  private static long getMaxSum(int[] numbers) {
    Map<Integer, List<Long>> cache = new HashMap<>();
    for (int i = 0; i < numbers.length; i++) {
      int currentNumber = numbers[i];
      if (currentNumber <= 0) {
        continue;
      }
      List<Integer> nextIndices = findNextIndices(i, numbers);
      List<Long> cachedResults = cache.getOrDefault(i, null);
      if (cachedResults == null) {
        for (int nextIndex : nextIndices) {
          long value = currentNumber + numbers[nextIndex];
          addToCache(cache, nextIndex, value);
        }
      } else {
        for (int nextIndex : nextIndices) {
          for (long cachedResult : cachedResults) {
            long value = cachedResult + numbers[nextIndex];
            addToCache(cache, nextIndex, value);
          }
        }
      }
    }
    return getMaxValue(cache);
  }

  public static void main(String[] args) throws IOException {
    int[] numbers = readNumbers();
    long maxSum = getMaxSum(numbers);
    System.out.println(maxSum);
  }
}

@@ -9,14 +9,25 @@
 ava.
-util.*
+io.BufferedReader
 ;%0Aim
@@ -35,38 +35,35 @@
 ort java.io.
-BufferedReader
+IOException
 ;%0Aimport jav
@@ -98,32 +98,87 @@
 rt java.
-io.IOException;%0A
+util.*;%0A%0A// https://www.hackerrank.com/challenges/max-array-sum/problem
 %0Apublic 
@@ -240,16 +240,59 @@
 E = %22 %22;
+%0A  private static final long SENTINEL = -1;
 %0A%0A  priv
@@ -615,32 +615,482 @@
 y();%0A    %7D%0A  %7D%0A%0A
+  /**%0A   * Because if the restriction of the problem (find the subset of non-adjacent%0A   * elements with the maximum sum), this method was designed to skip the next%0A   * element relative to the currentIndex and return the indices of the next%0A   * two positive elements.%0A   *%0A   * @param currentIndex Index of the numbers array we are currently evaluating.%0A   * @param numbers An array of numbers.%0A   * @return a List with at most two elements.%0A   */%0A
   private static
@@ -1518,24 +1518,337 @@
 dices;%0A  %7D%0A%0A
+  /**%0A   * Adds an element to a map only if the element is greater than the cached%0A   * element corresponding to the given key.%0A   *%0A   * @param cache A map we are using to store previously computed values.%0A   * @param key A possible key of the cache.%0A   * @param value A value to be inserted in the cache.%0A   */%0A
   private st
@@ -1885,32 +1885,20 @@
 er, 
-List%3C
 Long%3E
-%3E
  cache,
-%0A     
  int
@@ -1925,32 +1925,24 @@
     
-List%3CL
+l
 ong
-%3E
  cached
-Results
+Value
  = c
@@ -1968,101 +1968,49 @@
 ey, 
-new ArrayList%3C%3E());%0A    if (!cachedResults.contains(value)) %7B%0A      cachedResults.add(v
+SENTINEL);%0A    if (value %3E cachedV
 alue)
-;
+ %7B
 %0A   
@@ -2027,29 +2027,21 @@
 ut(key, 
-cachedResults
+value
 );%0A    %7D
@@ -2089,35 +2089,29 @@
 ap%3CInteger, 
-List%3C
 Long%3E
-%3E
  cache) %7B%0A  
@@ -2144,31 +2144,18 @@
 or (
-List%3CLong%3E cachedV
+long v
 alue
-s
  : c
@@ -2175,50 +2175,8 @@
 ) %7B%0A
-      for (long value : cachedValues) %7B%0A  
     
@@ -2223,32 +2223,24 @@
 : maxValue;%0A
-      %7D%0A
     %7D%0A    re
@@ -2329,19 +2329,13 @@
 er, 
-List%3C
 Long%3E
-%3E
  cac
@@ -2572,18 +2572,12 @@
     
-List%3CL
+l
 ong
-%3E
  cac
@@ -2585,17 +2585,16 @@
 edResult
-s
  = cache
@@ -2610,20 +2610,24 @@
 ault(i, 
-null
+SENTINEL
 );%0A     
@@ -2647,17 +2647,20 @@
 sult
-s
  == 
-null
+SENTINEL
 ) %7B%0A
@@ -2882,62 +2882,8 @@
 ) %7B%0A
-          for (long cachedResult : cachedResults) %7B%0A  
     
@@ -2938,34 +2938,32 @@
 dex%5D;%0A          
-  
 addToCache(cache
@@ -2987,20 +2987,8 @@
 e);%0A
-          %7D%0A
     

Improve solution to past test cases with no timeout.