@@ -0,0 +1,2577 @@
+import java.util.*;%0Aimport java.io.BufferedReader;%0Aimport java.io.InputStreamReader;%0Aimport java.io.IOException;%0A%0Apublic class MaxArraySum %7B%0A%0A  private static final String SPACE = %22 %22;%0A%0A  private static int%5B%5D readNumbers() throws IOException %7B%0A    try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) %7B%0A      reader.readLine(); // Skip array length line.%0A      String%5B%5D split = reader.readLine().split(SPACE);%0A      return Arrays.stream(split).mapToInt(Integer::parseInt).toArray();%0A    %7D%0A  %7D%0A%0A  private static List%3CInteger%3E findNextIndices(int currentIndex, int%5B%5D numbers) %7B%0A    List%3CInteger%3E nextIndices = new ArrayList%3C%3E();%0A    for (int i = currentIndex + 2; i %3C numbers.length; i++) %7B%0A      if (numbers%5Bi%5D %3E 0) %7B%0A        nextIndices.add(i);%0A        int next = i + 1;%0A        if (next %3C numbers.length && numbers%5Bnext%5D %3E 0) %7B%0A          nextIndices.add(next);%0A        %7D%0A        return nextIndices;%0A      %7D%0A    %7D%0A    return nextIndices;%0A  %7D%0A%0A  private static void addToCache(Map%3CInteger, List%3CLong%3E%3E cache,%0A      int key, long value) %7B%0A    List%3CLong%3E cachedResults = cache.getOrDefault(key, new ArrayList%3C%3E());%0A    if (!cachedResults.contains(value)) %7B%0A      cachedResults.add(value);%0A      cache.put(key, cachedResults);%0A    %7D%0A  %7D%0A%0A  private static long getMaxValue(Map%3CInteger, List%3CLong%3E%3E cache) %7B%0A    long maxValue = 0;%0A    for (List%3CLong%3E cachedValues : cache.values()) %7B%0A      for (long value : cachedValues) %7B%0A        maxValue = (value %3E maxValue) ? value : maxValue;%0A      %7D%0A    %7D%0A    return maxValue;%0A  %7D%0A%0A  private static long getMaxSum(int%5B%5D numbers) %7B%0A    Map%3CInteger, List%3CLong%3E%3E cache = new HashMap%3C%3E();%0A    for (int i = 0; i %3C numbers.length; i++) %7B%0A      int currentNumber = numbers%5Bi%5D;%0A      if (currentNumber %3C= 0) %7B%0A        continue;%0A      %7D%0A      List%3CInteger%3E nextIndices = findNextIndices(i, numbers);%0A      List%3CLong%3E cachedResults = cache.getOrDefault(i, null);%0A      if (cachedResults == null) %7B%0A        for (int nextIndex : nextIndices) %7B%0A          long value = currentNumber + numbers%5BnextIndex%5D;%0A          addToCache(cache, nextIndex, value);%0A        %7D%0A      %7D else %7B%0A        for (int nextIndex : nextIndices) %7B%0A          for (long cachedResult : cachedResults) %7B%0A            long value = cachedResult + numbers%5BnextIndex%5D;%0A            addToCache(cache, nextIndex, value);%0A          %7D%0A        %7D%0A      %7D%0A    %7D%0A    return getMaxValue(cache);%0A  %7D%0A%0A  public static void main(String%5B%5D args) throws IOException %7B%0A    int%5B%5D numbers = readNumbers();%0A    long maxSum = getMaxSum(numbers);%0A    System.out.println(maxSum);%0A  %7D%0A%7D%0A

Add first version of Max array sum solution: it works but is too slow.