[LSCS] Kadane’s Algorithm

개념 원리

1. 최대 합 연속 부분배열 ( Kadane’s Algorithm )

2. 아래의 코드 : 가능 한 한 최소값을 할당

int max = Integer.MIN_VALUE;

 

문제

1. 주어진 배열에 포함되는 연속 배열 중, 요소의 합이 가장 큰 값을 리턴하기

2. 단, 주어진 배열의 요소는 음수도 포함

3. 시간 복잡도 O(n)으로 풀기

 

나의 코드1 : 시간 복잡도를 맞추지 못한 코드

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

// 그냥 모든 연속 배열 중 가장 큰값
public static int LSCS(int[] arr) {
    ArrayList<Integer> list = new ArrayList<>();

    for(int i = 0; i < arr.length; i++) {
        int max = arr[i];
        list.add(max);
        for(int j = i+1; j < arr.length; j++) {
            max += arr[j];
            list.add(max);
        }
    }

    int output = list.get(0);
    for(int k=0; k < list.size(); k++) {
        if(output<=list.get(k)) output = list.get(k);
    }

    return output;
}

 

나의 코드2 : 연속 배열의 요소도 연속된 정수일 경우에만 합이 가능할 경우 (좀 더간 예제)

// 연속된 숫자가 나오는 연속 배열에서 합의 최대값을 구하는 방식
public static int LSCS2(int[] arr) {
    ArrayList<Integer> list = new ArrayList<>();
    int max = 0;

    for(int i = 0; i < arr.length; i++) {
        max += arr[i];
        for(int j = i+1 ; j < arr.length; j++) {
            if(arr[i]+1!=arr[j]) {
                list.add(max);
                max =0;
                break;
            }
            max += arr[j];
        }
    }

    int output = list.get(0);
    for(int k=0 ; k < list.size() ; k++) {
        if(list.get(k)>=output) output = list.get(k);
    }

    return output;
}

 

레퍼런스 코드 : 시간복잡도 O(n)을 맞춘 코드. 동적 프로그래밍(DP)

public class reference {
    public static void main(String[] args) {
        int output = LSCS(new int[]{1, 2, 3, -4, 5});
        int output2 = LSCS(new int[]{1,7,8,-10,100});
        int output3 = LSCS(new int[]{-10,-11,-12,-100});
        System.out.println(output); // --> 7 ([1, 2, 3, -4, 5])
        System.out.println(output2); // --> 7 ([1, 2, 3, -4, 5])
        System.out.println(output3); // --> 7 ([1, 2, 3, -4, 5])
    }

    public static int LSCS(int[] arr) {
        // 이중 저장 구조
        // 연속 배열의 합은 순차적으로 구하고, 최대값은 따로저장.
        // 최대값과 연속배열의 합을 비교하며 큰값만 교체해주는 구조
        // 만약, 모두 음수인 배열이면, 어차피 가장 큰 음수값 하나만 있는게 max임. 음수면 curSum을 0으로 초기화 하면 됨(더 더할필요 없으니까)
        int curSum = 0;
        int max = Integer.MIN_VALUE; // 음수를 포함하기 때문에 사용 가능한 최저 음수를 할당 : -2147483648이 최저값
        for(int i = 0; i < arr.length; i++) {
            curSum = curSum + arr[i];
            if(curSum > max) max = curSum;

            if (curSum < 0) {
                curSum = 0;
            }
        }
        return max;
    }
}

 

링크

깃 링크 https://github.com/PNUHCT/AlgorismStorage.git

참고 링크 https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/