LSCS 구하기

LSCS는 Largest Sum of Contiguous Subarray의 약자로, 연속된 부분배열의 합들 중 가장 큰 합을 의미합니다.

 

연속된 부분 배열이란 예를 들어서 전체 배열이 {1, 2, 3} 인 경우에 

{1}, {1,2}, {1,2,3}, {2}, {2,3}, {3} 과 같이 인접한 원소들로만 이루어진 집합을 의미합니다. 

이 배열의 LSCS는 부분배열 {1,2,3}의 원소의 합인 6이 됩니다.

 

원소들이 0이상의 정수라면 단순히 모든 원소를 다 더하면 LSCS가 되겠지만,

음수가 포함되는 경우는 조금 다른 결과가 나올 것입니다.

 

위의 문제를 만났을 때 배열의 index를 포인터 삼아 포인터를 옮겨가며 모든 부분배열 원소의 합을 각자 구한 뒤, 

그 중에서 가장 큰 값을 구하는 방법을 사용했습니다. IDE에서는 동작을 잘 하는 것 같은데, 코테 프로그램에서는 시간초과가 나왔습니다. 이렇게 저렇게 시도를 해보다가 효과적이면서도 간단한 로직이 있다는 것을 알게되었습니다. 

 

public static int LSCS(int[] arr) {

		int sum = 0; //부분배열의 합을 구할 변수
		int max = Integer.MIN_VALUE; //LSCS를 알아내기 위한 변수

		for(int i = 0; i < arr.length; i++) {
        
        	/* 1. 원소들을 순서대로 더하여 sum을 구하고 
                  sum이 max보다 큰지 확인하며 max 값을 구해나간다. 
            */
			sum += arr[i];
			if(sum > max) max = sum;
			if(sum < 0) sum = 0; 
            /* 2. 총합이 음수가 나오는 순간 뒤에 남은 값들을 더해도 최대값이 될 수 없으므로
               sum을 0으로 초기화한 다음 뒤에 남은 나머지 원소들을 마저 더해준다! */

		}

		return max;
}

 

위의 로직인데, 크게 두 가지 중요한 포인트가 있는 것 같았습니다.

1. 하나는 LSCS의 핵심인 연속된 원소들의 합을 구한다는 사실을 쉽게 이용하는 것입니다. 중간에 건너뛰게 되는 원소가 없이 순서대로 더하기 때문에 for loop을 이용해서 원소를 하나씩 더해갑니다. 

그리고 원소를 더한 값인 sum으로 max값을 구해 나갑니다. 양수가 계속 더해진다면 for loop이 진행될때마다 max값이 변경될 것입니다. 진행하면서 미리 max값을 구해놓기 때문에 연산 값을 기록해두는 memoization하고도 약간 유사하다고 생각이 들었습니다.

2. 두번째는 sum이 0보다 작아지는 순간을 잡아내는 것입니다. 이렇게 할 수 있다는 생각은 전혀 하지 못했기 때문에 참신하게 느껴졌고, 기억하고 있어야겠다고 생각했습니다. 앞의 원소를 다 더한 값이 음수라면 현재 더해야 하는 원소 값을 더했을 때 sum이 현재 더하는 원소보다 작아지기 때문에 연산을 멈추고 현재 원소부터 다시 시작해서 남은 원소들을 더해나가는 것이 더 유리합니다. 하지만 이 로직에서는 연산을 멈춘다기 보다는 sum이 음수가 되는 순간 sum을 0으로 만들어서 뒤의 원소부터 다시 sum을 시작하는 것처럼 만들어주고 있습니다. 이렇게도 수행할 수 있다는 것을 알게되어서 나중에 적용할 일이 있다면 꼭 적용해서 풀이해보려고 합니다.

 

제가 처음에 풀이했던 방식은 아래 코드와 같습니다. 

 

 public static int LSCS(int[] arr) {

        int indexA = 0;
        int indexB = 0;
        int sum = 0;
        ArrayList<Integer> sums = new ArrayList<>();
        if(arr.length == 1) return arr[0];

        while(!((indexA == arr.length -1) && (indexB == arr.length - 1))) {
            
            if(indexA == indexB) {
                sums.add(arr[indexA]);
                indexB++;
                continue;
            }
            
            for(int i = indexA; i <= indexB; i++) {
                sum += arr[i];
            }
            
            sums.add(sum);
            sum = 0;
            indexB++;
            if(indexB == arr.length) {
                indexA++;
                indexB = indexA;
            }
            
        }

        sums.add(arr[indexA]);

        return sums.stream().mapToInt(n -> n).max().orElse(0);
    }

 

코드가 좀 깔끔하지 못하지만 일단 동작은 하는 구나 생각했는데 제한 시간보다 수행에 시간이 오래 걸리는 풀이었나봅니다.

간단하면서 나중에 응용하기도 좋을 것 같은 풀이를 알게되었으니 꼭 다음번에 적용해보고 이 문제도 몇번 더 풀어보면서 익히려고 합니다.

감사합니다!