fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int main(void)
  6. {
  7. 	int n, a[1000], left[1000], right[1000];	//n = 수열 a의 크기, a = 입력된 수열, left = 왼쪽부터 시작하는 LIS, right = 오른쪽부터 시작하는 LIS
  8. 	int result = 0;
  9. 	cin >> n;
  10.  
  11. 	for (int i = 0; i < n; i++)
  12. 		cin >> a[i];
  13.  
  14. 	for (int i = 0; i < n; i++)			//왼쪽에서 LIS 알고리즘 적용
  15. 	{
  16. 		left[i] = 1;
  17. 		for (int j = 0; j <= i; j++)
  18. 			if (a[j] < a[i] && left[i] < left[j] + 1)
  19. 				left[i]++;
  20. 	}
  21.  
  22. 	for (int i = n - 1; i >= 0; i--)	//오른쪽부터 LIS 알고리즘 적용
  23. 	{
  24. 		right[i] = 1;
  25. 		for (int j = n - 1; j >= i; j--)
  26. 			if (a[j] < a[i] && right[i] < right[j] + 1)
  27. 				right[i]++;
  28. 	}
  29.  
  30. 	for (int i = 0; i < n; i++)			//왼쪽과 오른쪽의 합이 제일 큰 값 찾기
  31. 		if (result < left[i] + right[i])
  32. 			result = left[i] + right[i];
  33. 	cout << result - 1;					//중복되는 중복값 제거로 인한 -1
  34. 	return 0;
  35. }
Success #stdin #stdout 0s 4648KB
comments (?)
stdin
copy 
10
1 5 2 1 4 3 4 5 2 1
stdout
copy 
7
https://ideone.com/2GTUre
language:
C++ (gcc 8.3)
created:
3 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!