11054_가장 긴 바이토닉 부분 수열

11054번 긴 바이토닉 수열

 - 처음 보고 LIS와 LIS를 합한 문제라고 생각했다. 그래서 먼저 짠 LIS에다가 for문을 하나 더 넣어서 알고리즘을 맞췄는데 왠일인지 값이 나오지 

않았다. 그래서 위와 같이 값이 들어가는 곳에 cout을 통해 console을 보니 내가 dp[i] += max를 for(j)안에 넣어서 이게 계속 반복된는 

것 이었다. 첫번째 LIS의 경우 문제되지 않으나 두번째는 누적해서 더해주므로 문제가 되었다. 그래서 for(j)밖으로 위의 명령문을 

빼주니 문제는 해결되었다.

그러나... 더 큰문제가 기다리고 있엇는데...

작은수를 찾는것이므로 처음은 앞에서부터 탐색했는데

뒤는 뒤에서부터 탐색하다간 아 그럼 작은걸 하면되겠구나.... 이생각을 지금하네

아무튼 나는 앞의 과정을 따라하기 위해 어리석게 뒤에서부터 연산을 시작했다.

그래서 코드는

위와 같다.

이건 맨뒤에서 부터 차례대로 비교하여 LIS를 찾는 것이다. 

여기서 max+1이 중요한데 +1을 해주지않으면 다른 dp값에 지장을 주므로 여기서 +1을 해준다음

결과를 도출할떄 2번 더해진 수에 대해 -1을 해주었다.