fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #define mx 1000
  5. int n=7;
  6. int value[]={-100000,5,0,9,2,7,3,4};
  7. int dp[mx],dir[mx];
  8. int longest(int u)
  9. {
  10. 	if(dp[u]!=-1) return dp[u];
  11. 	int maxi=0;
  12. 	for(int v=u+1;v<=n;v++) //১ম শর্ত,v>u
  13. 	{
  14. 		if(value[v]>value[u]) //২য় শর্ত, value[v]>value[u]
  15. 		{
  16. 			if(longest(v)>maxi) //সর্বোচ্চ মানটা নিবো
  17. 			{
  18. 				maxi=longest(v);
  19.                                 dir[u]=v;
  20.  
  21. 			}
  22. 		}
  23. 	}
  24. 	dp[u]=1+maxi; //১ যোগ হবে কারণ u নম্বর নোডটাও পাথের মধ্যে আছে
  25. 	return dp[u];
  26. }
  27.  
  28. void solution(int start)
  29. {
  30. 	while(dir[start]!=-1)
  31. 	{
  32. 		printf("index %d value %d\n",start,value[start]);
  33. 		start=dir[start];
  34. 	}
  35. }
  36.  
  37.  
  38. int main()
  39. {
  40. 	//READ("in");
  41. 	memset(dp,-1,sizeof dp);
  42.         memset(dir,-1,sizeof dir);
  43. 	int LIS=0,start;
  44. 	for(int i=1;i<=n;i++)
  45. 	{
  46. 		printf("longest path from: %d\n",longest(i));
  47. 		if(longest(i)>LIS)
  48. 		{
  49. 			LIS=longest(i);
  50. 			start=i;
  51. 		}
  52. 	}
  53. 	printf("LIS = %d Starting point %d\n",LIS,start);
  54. 	solution(start);
  55.  
  56. 	return 0;
  57. }
  58.  
Success #stdin #stdout 0s 3304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
longest path from: 2
longest path from: 4
longest path from: 1
longest path from: 3
longest path from: 1
longest path from: 2
longest path from: 1
LIS = 4 Starting point 2
index 2 value 0
index 4 value 2
index 6 value 3
https://ideone.com/DDohZj
language:
C++ (gcc 8.3)
created:
9 years 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!