[BOJ] 11055번 가장 큰 증가 부분 수열

복기

메모이제이션을 하자

코드

• C++ 17

#include <stdio.h>   #define MAX(a, b) ((a) > (b) ? (a) : (b))   int N, Ans; int Arr[1001];   // Memo[i] : i번째를 수열의 마지막 수라고 할 때, 그 수열의 합 // Memo[i] = Memo[j] + Arr[i] if Arr[j] < Arr[i] int Memo[1001];   int main() {     scanf("%d", &N);     for (int i = 0; i < N; ++i)     {         scanf("%d", &Arr[i]);         Memo[i] = Arr[i];           for (int j = 0; j < i; ++j)         {             if (Arr[j] < Arr[i] && Memo[i] < Memo[j] + Arr[i])                 Memo[i] = Memo[j] + Arr[i];         }         Ans = MAX(Ans, Memo[i]);     }       printf("%d", Ans); }

• C# 6.0

using System; using System.Collections.Generic; using System.Security.Cryptography.X509Certificates;   namespace Csharp {     class Program     {         static int[] Arr = new int[1001];         static int[] Memo = new int[1001];         static int N, Ans;           static void Main(string[] args)         {             N = Convert.ToInt32(Console.ReadLine());             var inputs = Console.ReadLine().Split();             for (int i = 0; i < N; ++i)             {                 Memo[i] = Arr[i] = Convert.ToInt32(inputs[i]);                 for (int j = 0; j < i; ++j)                 {                     if (Arr[j] < Arr[i] && Memo[i] < Memo[j] + Arr[i])                         Memo[i] = Memo[j] + Arr[i];                 }                 Ans = Math.Max(Ans, Memo[i]);             }             Console.Write(Ans);         }     } }

• Python 3

from sys import stdin input = stdin.readline   N = int(input()) Arr =  list(map(int, input().split())) Memo = [0] * N Ans = 0   for i in range(N):     Memo[i] = Arr[i]     for j in range(i):         if Arr[j] < Arr[i] and Memo[i] < Memo[j] + Arr[i]:             Memo[i] = Memo[j] + Arr[i]     Ans = Memo[i] if Memo[i] > Ans else Ans   print(Ans)