tose33

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net d[n] : a[n]을 포함하는 연속된 부분 수열들 중 그 합이 최대인 값. 수열이 다음과 같다고 하자. d[0]은 자기자신 밖에없으므로 그냥 a[0]이다. 그럼 d[1]은 몇일까? 수열이 {10, -4}이므로 원소 둘 다 더해서 10 + (-4) = 6 일수 있고, 아니면 앞의 숫자는 버리고 -4부터 시작해서 그냥 -4 일수 있다. 둘 중 큰 값은 전자 6이다. d[2]를 보자. 수열은 {10, -4, 3..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 가장 긴 증가하는 부분수열 문제와 비슷하지만 길이를 구하는게 아닌 가장 큰 수의 합을 구하는 문제. 가장 긴 증가하는 부분수열 문제에서는 이전 숫자와 비교하면서 계속 길이를 갱신했다면 이번에는 더하면서 합을 갱신한다. 각각 의 합을 갱신하면서 가장 큰 합도 계속 갱신한다. import sys n = int(input()) s = [0] ..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 부분수열이란, 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족하는 수열이다. 즉 여러번의 증가와 감소가 나타나지 않는 수열이다. 예를들어 {10,20,30,25,20}. 그리고 {10,20,30,40}, {50,40,25,10}처럼 한번의 증가 or 감소만 있어도 바이토닉 부분수열이다. {1, 2, 3, 2, 1, 2, 3, 2,..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 이 문제는 이 전에 한 11053. 가장 긴 증가하는 부분수열 (https://tose33.tistory.com/18)과 거의 똑같다. 가장 긴 증가하는 부분수열 문제에서 A[i]값보다 작은 A값 들 중 가장 큰 d값에서 1을 더한것이 D[i]였다. 예를들어 i = 4일때, 수열은 {10, 20, 10, 30} 이고, ..