[백준] 11055번: 가장 큰 증가하는 부분 수열 [C#]

 

 

using System.IO;
using System.Text;
using System.Linq;
using System.Reflection.PortableExecutable;
using System.Security.Cryptography;
 
namespace 연습장
{
    internal class Program
    {
        static StringBuilder sb = new StringBuilder();
        static void Main(string[] args)
        {
            using var reader = new StreamReader(Console.OpenStandardInput());
            using var print = new StreamWriter(Console.OpenStandardOutput());
 
            _11055_boj boj = new _11055_boj();
 
            boj.boj_11055();
 
        }
    }
    internal class _11055_boj
    {
        public void boj_11055()
        {
            int n = int.Parse(Console.ReadLine());
 
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
 
            int[] dp = new int[n];
            dp[0] = arr[0];
            
            for (int i = 1; i < n; i++)
            {
                int max = 0;
                for (int j = i - 1; j >= 0; j--)
                    if (arr[j] < arr[i] && max < dp[j])
                        max = dp[j];
                dp[i] = arr[i] + max;
            }
            Console.WriteLine(dp.Max());
        }
    }
}
 

 

가장 큰 수열의 합을 구하는 것이기 때문에 이전의 값들 중 max의 값을 가져와야 했지만, 그런 과정 없이 가장 가까운 값을 가져와서 합을 해줘서 틀렸었다.