[알고리즘] LSCS 알고리즘

Largest Sum Contiguous Subarray (Kadane's Algorithm) - GeeksforGeeks

LSCS 

Largest Sum of Contiguous Subarray.

주어진 배열의 연속된 부분 배열의 합을 구한다고 할 때, 이중 가장 큰 값을 구하는 알고리즘이다.

---

1. 문제의 흐름을 생각해보자.

int[] arr = { -2, -3, 4, -1, -2, 1, 5, -3 };

정수 배열 arr이 위라고 가정을 하고 접근해보자.

여기서 구하는 값은 배열 arr의 합 중 가장 큰 값이다.

그렇다면 max 값을 작은 음수 값으로 설정한 후, arr의 길이 만큼 배열을 돌면서 합을 구해야 할 것이다.

 

public class LSCS{
	public static void main(String[] args){
    	int[] arr = { -2, -3, 4, -1, -2, 1, 5, -3 };
        
        System.out.println(solution(arr));
    }
    
    // 배열의 합 구하는 함수
    public static solution(int[] arr){
    	
        // max 값을 작은 수로 지정
        int max = -20000;
        
        // 배열의 합을 구할 변수 선언
        int sum = 0;
        
        // 배열의 길이만큼 반복하면서 구하기
        for(int i = 0; i < arr.length; i++){
        	sum += arr[i];
        }
    }
}

 

2. 반복문 안에 들어갈 조건문을 생각해보자

0번째 인덱스와 1번째 인덱스를 더하면 -5가 나온다.

만약 더한 값이 음수이면 그냥 0으로 두고 더해도 상관이 없다.

왜냐하면, 구하는 값은 연속된 부분의 배열의 합 중 가장 큰 값이기 때문이다.

0번째 인덱스와 1번째 인덱스를 제외하고, 2번째 인덱스부터 그 다음 연속된 인덱스의 값을 더해도 연속된 부분의 배열의 합이다.

따라서 아래의 코드를 생각해 볼 수 있다.

if(sum < 0){sum = 0;}

이렇게 되면, sum의 값이 0으로 초기화 된다. 

그럼 그 전의 값이 최대값이 존재하더라도, 알 수 없다.

따라서 계속해서 더할 때, sum의 값이 가장 크다면 해당 값이 max의 값이 되어야 한다.

 

❗️ max 값을 작은 음수로 지정하고, sum = 0으로 굳이 지정해서 비교하는 이유는 배열 요소가 음수만 존재할 수 있기 때문 ❗️

 

풀이

public class LSCS{
	public static void main(String[] args){
    	int[] arr = { -2, -3, 4, -1, -2, 1, 5, -3 };
        
        System.out.println(solution(arr));
    }
    
    // 배열의 합 구하는 함수
    public static solution(int[] arr){
    	
        // max 값을 작은 수로 할당
        int max = -20000;
        
        // 배열의 합을 구할 변수 선언 및 초기화
        int sum = 0;
        
        // 배열의 길이만큼 반복하면서 구하기
        for(int i = 0; i < arr.length; i++){
        	sum += arr[i];
            
            // 만약 sum의 값이 max의 값보다 크면, 해당 값이 max
            if(sum > max){max = sum;}
            
            // sum의 값이 음수가 되면, 다시 시작
            if(sum < 0){sum = 0;}
        }
        
        return max;
    }
}