fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		// your code goes here
  13. 		int[] nums = {1, 5, 6, 1, 5, 1, 5};
  14.  
  15. 		int n = nums.length;
  16. 		int[][][] dp = new int[n + 2][n + 2][4];
  17.  
  18. 		int sum1 = nums[n-1] + nums[n-2];
  19. 		int sum2 = nums[1] + nums[2];
  20. 		int sum3 = nums[1] + nums[n-1];
  21.  
  22. 		for(int i = 0; i < n - 1; i++){
  23.  
  24. 			int sum = nums[i] + nums[i+1];
  25. 			int g = 1;
  26.  
  27. 		if(sum == sum1){
  28. 		dp[i][i+1][1] = Math.max(g, dp[i][i+1][1]);
  29. 		}
  30.  
  31. 		if(sum == sum2){
  32. 		dp[i][i+1][2] = Math.max(g, dp[i][i+1][2]);
  33. 		}
  34.  
  35. 		if(sum == sum3){
  36. 		dp[i][i+1][3] = Math.max(g, dp[i][i+1][3]);
  37. 		}
  38.  
  39. 		}
  40.  
  41. 		for(int len = 3; len <= n; len++){
  42. 			for(int start = 0; start <= n - len; start++){
  43. 				int end = start + len - 1;
  44.  
  45. 				int g = 1;
  46. 				int sum = nums[start] + nums[start + 1];
  47.  
  48. 				if(sum == sum1){
  49. 					dp[start][end][1] = Math.max(dp[start][end][1], g + dp[start + 2][end][1]);
  50. 				}
  51. 				if(sum == sum2){
  52. 					dp[start][end][2] = Math.max(dp[start][end][2], g + dp[start + 2][end][2]);
  53. 				}
  54. 				if(sum == sum3){
  55. 					dp[start][end][3] = Math.max(dp[start][end][3], g + dp[start + 2][end][3]);
  56. 				}
  57.  
  58.  
  59. 				sum = nums[end - 1] + nums[end];
  60.  
  61. 				if(sum == sum1){
  62. 					dp[start][end][1] = Math.max(dp[start][end][1], g + dp[start][end - 2][1]);
  63. 				}
  64. 				if(sum == sum2){
  65. 					dp[start][end][2] = Math.max(dp[start][end][2], g + dp[start][end - 2][2]);
  66. 				}
  67. 				if(sum == sum3){
  68. 					dp[start][end][3] = Math.max(dp[start][end][3], g + dp[start][end - 2][3]);
  69. 				}
  70.  
  71.  
  72. 				sum = nums[start] + nums[end];
  73.  
  74. 				if(sum == sum1){
  75. 					dp[start][end][1] = Math.max(dp[start][end][1], g + dp[start + 1][end - 1][1]);
  76. 				}
  77. 				if(sum == sum2){
  78. 					dp[start][end][2] = Math.max(dp[start][end][2], g + dp[start + 1][end - 1][2]);
  79. 				}
  80. 				if(sum == sum3){
  81. 					dp[start][end][3] = Math.max(dp[start][end][3], g + dp[start + 1][end - 1][3]);
  82. 				}
  83. 			}
  84. 		}
  85.  
  86. 		System.out.println(Math.max(dp[0][n-1][1], Math.max(dp[0][n-1][2], dp[0][n-1][3])));
  87.  
  88. 	}
  89. }
Success #stdin #stdout 0.07s 54532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/CleCi6
language:
Java (HotSpot 12)
created:
18 hours 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!