C#으로 숫자 배열에서 가장 긴 연속 증가 부분 수열의 길이 찾는 방법

C#에서 숫자 배열에 포함된 가장 긴 연속 증가 부분 수열(Longest Continuous Increasing Subsequence)의 길이를 구하는 방법을 알아보겠습니다.

알고리즘 개요

LongestIncreaingSubsequence 메서드는 배열 안에서 연속된 값들이 증가하는 구간 중 가장 긴 구간의 길이를 정수로 반환합니다. 메서드 내부의 for 루프가 배열을 순차적으로 순회하면서 숫자들의 흐름을 추적하고, 최종 결과는 Math.Max를 통해 계산됩니다.

모든 요소를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(N)입니다.
별도의 저장 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.

복잡도 분석

시간 복잡도 – O(N)
공간 복잡도 – O(1)

예시

입력 – {2, 4, 6, 5, 8}

출력 – 3

위 예시에서 가장 긴 연속 증가 구간은 2 → 4 → 6이며, 이때의 길이는 3입니다. 5에서 증가 흐름이 끊기지만, 이후 5 → 8 구간은 길이가 2로 더 짧기 때문에 최대값은 3이 됩니다.

구현 코드

public class Arrays{
   public int longestIncreaingSubsequence(int[] nums){
      if (nums == null || nums.Length == 0){
         return -1;
      }
      int res = 0, count = 0;
      for (int i = 0; i < nums.Count(); i++){
         if (i == 0 || nums[i] > nums[i - 1]){
            count++;
            res = Math.Max(res, count);
         }
         else{
            count = 1;
         }
      }
      return res;
   }
}

static void Main(string[] args){
   int[] nums = { 1, 3, 5, 4, 7 };
   Console.WriteLine(s.longestIncreaingSubsequence(nums));
}

코드 동작 원리

첫 번째 요소이거나(i == 0) 현재 요소가 바로 앞 요소보다 크면 count를 1 증가시킵니다.
증가 흐름이 끊기면 count를 1로 초기화하여 새로운 구간을 다시 셉니다.
res에는 항상 지금까지 나타난 최대 구간 길이가 저장되며, 반복이 끝나면 이 값이 반환됩니다.

실행 결과

입력 배열 {1, 3, 5, 4, 7}에서 가장 긴 연속 증가 구간은 1 → 3 → 5이므로 출력은 다음과 같습니다.