none
c언어 가장 긴 증가하는 수열 RRS feed

  • 질문

  • 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

    증가하는 부분 수열은 연속되는 수열에서 다음 숫자가 바로 앞의 숫자보다 크거나 같은 부분을 의미한다.

    예를 들어, 수열 A = (10, 30, 10, 20, 20, 10) 인 경우에 가장 긴 증가하는 부분 수열은 10 20 20 이고, 길이는 3, 합은 50이다.

    입력

    첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

    출력

    첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이와 합을 출력한다. (가장 긴 부분 수열이 같은 길이로 두 번 이상 나올 경우 앞의 것의 합을 출력한다.)

    두 번째 예시에서 가장 긴 부분 수열은 길이 4인데 [2, 3, 5, 6]과 [3, 6, 7, 8]과 [2, 6, 17, 28]이다. 길이가 같으므로 제일 앞에 나온 부분수열의 합 16을 출력한다.

    예시 데이터


    Input Output
    6
    10 30 10 20 20 10
    10 20 20    
    30
    5 2 3 5 6 1 6 23 6 4 23 6 4 3 6 7 8 4 3 6 7 4 6 7 4 6 1 2 6 17 28
    1 2 6 17 28

    이 부분인데 당최 감이 안잡힙니다. 도와주세요.

    2018년 9월 22일 토요일 오후 12:51