C++에서 가장 긴 연속 증가 부분 수열(LCIS) 구하기

정수 배열이 주어졌을 때, 그중 가장 긴 연속 증가 부분 배열의 길이를 찾는 문제입니다.

예를 들어 입력이 [2,4,6,5,8]이라면 출력은 3이 됩니다. 가장 긴 연속 증가 부분 수열이 [2,4,6]이고, 그 길이가 3이기 때문입니다.

문제 해결 접근 방법

이 문제는 배열을 한 번만 순회하면 되는 간단한 선형 탐색으로 해결할 수 있습니다. 알고리즘 단계는 다음과 같습니다.

배열(nums)의 크기가 1 이하라면, 배열의 크기를 그대로 반환합니다.
answer := 1, count := 1 로 초기화합니다.
i := 0부터 시작하여 i가 배열 크기 미만일 때까지 i를 1씩 증가시키며 반복합니다.
- nums[i] < nums[i + 1] 인 경우(증가가 이어지는 경우):
  - count를 1 증가시킵니다.
  - answer에 answer와 count 중 더 큰 값을 저장합니다.
- 그렇지 않은 경우(증가가 끊긴 경우):
  - count를 1로 초기화하여 새로운 부분 수열을 시작합니다.
반복이 끝나면 answer를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

구현 예제

아래 C++ 코드를 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.size() <= 1)
            return nums.size();
        int answer = 1, count = 1;
        for (int i = 0; i < nums.size() - 1; i++) {
            if (nums[i] < nums[i + 1]) {
                count++;
                answer = max(answer, count);
            }
            else {
                count = 1;
            }
        }
        return answer;
    }
};
main(){
    Solution ob;
    vector<int> v = {2,4,6,5,8};
    cout << (ob.findLengthOfLCIS(v));
}

입력

{2,4,6,5,8}