[LIS] 주어진 숫자형 배열의 부분배열 중, 엄격한 오름차순인 가장 긴 부분배열의 최대길이

문제

: [LIS] 주어진 숫자형 배열의 부분배열 중, 엄격한 오름차순인 가장 긴 부분배열의 최대길이

: 여기서 '엄격한 오름차순'이란, 배열 내 모든요소에 n번째 < n+1번째가 성립해야함

ex) {1,3,5,7,9} 는 통과

ex) {1,3,7,5,9} 는 불가

---

참고

Arrays.fill(arr, value) : arr에 value값으로 싹 다 채우는 메서드

 

---

나의 코드

: 모든 부분 배열(순열)을 구해서 비교하는 방식

import java.util.*;

public class LIS {
    public static void main(String[] args) {
        int output = LIS(new int[]{3, 2});
        System.out.println(output); // --> 1 (3 or 2)

        output = LIS(new int[]{3, 10, 2, 1, 20});
        System.out.println(output); // --> 3 (3, 10, 20)
    }

    // 모든 부분 배열을 ArrayList에 받아 비교하는 부분
    public static int LIS(int[] input) {
        int max = 1;
        Stack<Integer> stack = new Stack<>();
        ArrayList<int[]> list = new ArrayList<>();

        search(stack, 0, input, list);

        for(int i = 0; i < list.size(); i++) {
            int[] tempArr = list.get(i);
            for(int j = 0; j < tempArr.length-1 ; j++) {
                if(tempArr[j]>=tempArr[j+1]) break;
                if(j==tempArr.length-2 && max<tempArr.length) max=tempArr.length;
            }
        }
        return max;
    }

    // 모든 부분 배열을 생성해서 ArrayList에 담아주는 부분
    private static void search(Stack<Integer> stack, int k, int[] input, ArrayList<int[]> list) {
        if(k >= input.length) {
            int[] temp = new int[stack.size()];
            Stack<Integer> stack2 = new Stack<>();
            for(int i = 0; i < temp.length; i++) {
                stack2.push(stack.pop());
            }
            for(int i = 0; i < temp.length; i++) {
                temp[i]=stack2.peek();
                stack.push(stack2.pop());
            }
            list.add(temp);
        }
        else {
            stack.add(input[k]);
            search(stack, k + 1, input, list);

            stack.pop();
            search(stack, k + 1, input, list);
        }
    }
}

---

레퍼런스

: 특정 인자까지 도달하는 경우를 카운트해서 최대값 구해 리턴하는 방식

import java.util.Arrays;

public class reference {
    public static void main(String[] args) {
//        int output = LIS(new int[]{3, 2});
//        System.out.println(output); // --> 1 (3 or 2)

        int output = LIS(new int[]{3, 10, 2, 1, 20});
        System.out.println(output); // --> 3 (3, 10, 20)
    }

    public static int LIS(int[] arr) {
        int N = arr.length;
        int[] lis = new int[N]; // 배열의 특정 인자까지 도달할 수 있는 경우를 카운트하는 배열
        Arrays.fill(lis, 1); // 자기 자신만 카운트하는건 무조건 있으니 전부 1가지 경우는 있는걸로 시작
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                    lis[i] = lis[j] + 1; // 만약 무탈히 도달하면 카운트 +1
                }
            }
        }
        return Arrays.stream(lis).max().getAsInt();  // lis에서 카운트 한 애들 중 가장 큰 애 리턴
    }
}

---

깃 링크

https://github.com/PNUHCT/AlgorismStorage.git