I implemented my solution (iterative) to this problem in python and it worked, I generated some crazy test cases and it worked ok, manually checked some other cases and all good. When I submitted it it was giving me NZEC every single time, I then decided to give it a shot in java, so I did, it worked as expected, but then again, when I uploaded it BANG! NZEC hit me right in my face. I have no clue where is the mistake...
import java.util.*;
class Farida {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = Integer.parseInt(sc.nextLine());
for (int i = 1; i <= t; i++) {
int n = Integer.parseInt(sc.nextLine());
long sol = 0;
if (n > 0) {
String line = sc.nextLine();
if (!line.equals("")) {
String[] monsters_str = line.split(" ");
long[] monsters = new long[n];
for (int j = 0; j < n; j++) {
monsters[j] = Long.parseLong(monsters_str[j]);
}
//Algorithm to solve problem: I solve from the smallest to the biggest problem, from the last monster to the first
for (int k = n-1; k >= 0; k--) {
long s2 = 0;
long s1 = 0;
if (k+2 < n) {
s2 = monsters[k+2];
}
if (k+1 < n) {
s1 = monsters[k+1];
}
monsters[k] = Math.max(monsters[k]+s2,s1);
}
// En monsters[0] queda la solucion del problema
sol = monsters[0];
}
}
System.out.println("Case "+i+": "+sol);
}
}
}