fork download 
  1. import java.util.*;
  2. /* package whatever; // don't place package name! */
  3. /*  Given an array of integers(positive as well as negative) ,select some elements from this array(select a subset) such that:-
  4.  
  5. 1. Sum of those elements is maximum(Sum of the subset is maximum) .
  6.  
  7. 2. No two elements in the subset should be consecutive.
  8.  
  9. Example :- {2,4,6,7,8}
  10.  
  11. Answer:- {2+6+8=16}
  12. */
  13.  
  14. import java.util.*;
  15. import java.lang.*;
  16. import java.io.*;
  17.  
  18. /* Name of the class has to be "Main" only if the class is public. */
  19. class Ideone
  20. {
  21. 	public static void main (String[] args) throws java.lang.Exception
  22. 	{
  23. 		Scanner sc=new Scanner(System.in);
  24. 		// your code goes here
  25. 		int n=sc.nextInt();
  26. 		int a[]=new int[n+1];
  27. 		for(int i=1;i<=n;i++)
  28. 		a[i]=sc.nextInt();
  29.  
  30. 		int dp[]=new int[n+1];
  31.  
  32. 		dp[0]=0;
  33. 		dp[1]=Math.max(a[1],0);
  34. 		dp[2]=Math.max(a[2],dp[1]);
  35.  
  36. 		for(int i=3;i<=n;i++)
  37. 		{
  38. 			dp[i]=Math.max(a[i]+dp[i-2], dp[i-1]);
  39. 		}
  40.  
  41. 		System.out.println(dp[n]);
  42.  
  43.  
  44. 	}
  45. }
Success #stdin #stdout 0.15s 54464KB
comments (?)
stdin 
5
2 4 6 7 8
stdout 
16
https://ideone.com/zt0I6d
language:
Java (HotSpot 12)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!