[LeetCode] Maximum Subarray

문제

image

  • 숫자로된 배열이 주어졌을 때, 가장 큰 합계를 가지는 연속적인 부분 배열의 합계를 반환해라

    • 최소 한 개 이상의 숫자를 포함하는 부분 집합이어야 한다.

    • 배열은 contiguous(연속적)이어야 한다.

풀이법

  • 최대부분합을 구하는 문제이다.

브루트 포스(Brute Force)

image

  • 단순 이중 for문으로 모든 경우를 탐색하는 방식이다.

  • 가능한 모든 부분 배열의 합을 구하고 이에 대한 최대값을 구하기 때문에 시간복잡도는 O(N³)이다.

  • 이때 prefixSum을 먼저 계산해두고 for문이 돌때마다 하나씩 빼면서 풀면 시간복잡도가 O(N²)이다.

분할 정복(Divide and Conquer)

image

  • Middel 구간 합을 구할 때는 for loop가 돌고, Left와 Right를 구할 때는 배열의 갯수만큼 재귀적으로 반복하기 때문에 시간복잡도는 O(nlog₂n) 이다.

동적계획법(Dynamic Programming)

image

  • 더 간단하게 풀기위해서 동적 계획법을 활용한 카데인 알고리즘을 이용하면 시간복잡도 O(N)으로 문제를 해결할 수 있다.

  • 동적 계획법은 재귀호출이 아닌 작은 문제의 값을 어딘가에 저장해두고 큰 문제를 해결할 때, 재사용하는 방법이라고 볼 수 있다.

  • 작은 문제의 solution들은 겹칠 수 있다.

// 문제 : 1부터 n까지의 합을 구하기
sum(n) = (1 + 2 + 3 + ... + n)
       = (1 + ... + n-1) + n

// 분할 정복법(재귀 호출)
sum(n) = sum(n-1) + n 
sum(1) = 1

// 동적계획법 (값을 저장해두고 재사용) 
S[n] = S[n-1] + n 
S[1] = 1

해결

  • newSum에 범위의 합계, max에 최대 범위의 합을 저장해두고 새로운 값과 비교해가면서 값을 변경한다.

  • 가장 처음에 newSum과 max에는 배열의 첫번째 값이 저장되어야 한다. 비교할 대상이 없기 때문이다.

  • 다음부터는 저장된 newSum와 (subArray + 배열의 i번째 index의 값)를 비교하여 더 큰 값을 newSum에 담는다.

  • 이렇게 구해진 newSum값을 기존의 max값과 비교하여 더 큰 값을 max에 담는다.

알고리즘 순서

  • nums[0] 그림1

  • nums[1] 그림2

  • nums[2] 그림3

  • nums[3] 그림4

  • nums[4] 그림5

  • nums[5] 그림6

  • nums[6] 그림7

  • nums[7] 그림8

  • nums[8] 그림9

코드

// 문제 : https://leetcode.com/problems/maximum-subarray/

public class T13_MaximumSubarray {
    public static void main(String[] args){
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        T13_MaximumSubarray t13 = new T13_MaximumSubarray();
        int result = t13.maxSubArray(nums);
        System.out.println(result);
    }
    public int maxSubArray(int[] nums) {
        int newSum = nums[0];
        int max = nums[0];

        for(int i=1; i<nums.length; i++) {
            newSum = Math.max(nums[i],nums[i]+newSum);
            max = Math.max(newSum, max);
        }
        return max;
    }
}

참고