2022.02.08 [백준] C# 가장 긴 증가하는 부분 수열

 

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

---

풀이

이 문제는 이중 for문을 이용하여 num[i]가 num[j](i>j)보다 크면 cnt 값을 비교하여 크면 max값에 cnt[j]값 대입하는 형식으로 해결했습니다.

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[] num;
    static int[] cnt;
 
    static int Cal(int n)
    {
        int max = 1;
        for(int i = 2; i <= n; i++)
        {
            for (int j = 1; j < i; j++)
            {
                if (num[i] > num[j])
                {
                    cnt[i] = Math.Max(cnt[i], cnt[j] + 1);
                    
                }
                if (max < cnt[i])
                {
                    max = cnt[i];
                }
            }
        }
        return max;
    }
 
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        string[] s = sr.ReadLine().Split();
        num = new int[n + 1];
        cnt = new int[n + 1];
        for (int i = 1; i <= n; i++)
        {
            num[i] = int.Parse(s[i - 1]);
            cnt[i] = 1;
        }
        
        sw.WriteLine(Cal(n));
        sr.Close();
        sw.Close();
    }
}