I solved problem (http://www.spoj.com/problems/FARIDA/) using DP. For storage purpose i am using HashMap but why am i getting TLE ?
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class FARIDA {
public static long maxC(Map<String, Long> map, long c[], int s, int e)
{
if(s>e)
return 0;
if(map.containsKey(s+"|"+e))
return map.get(s+"|"+e);
if(s==e)
map.put(s+"|"+e, c[s]);
else
map.put(s+"|"+e, Math.max(c[s]+ maxC(map,c,s+2,e),maxC(map,c,s+1,e)));
return map.get(s+"|"+e);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int j=1;j<=t;j++)
{
int n=in.nextInt();
long c[]= new long[n];
for(int i=0; i<n; i++)
c[i]=in.nextLong();
Map<String, Long> map = new HashMap<String, Long>();
System.out.println("Case "+j+": "+maxC(map,c,0,n-1));
}
in.close();
}
}