kadane algorithm, maximum sum subarray

Kadane

find the max sum of contiguous subarray of given array.
-1, -2, 3, 4, -5, 6

위의 경우 {3,4,-5,6} = 8이 된다.

naive

start, end index를 정해서 for loop 2번 하면 구할 수 있음. O(n^2)

dp

dp[i] -> index i 에서 끝나는 subarray 중에서 쵀대값. 이라고 정의 하면

dp[i] = max(dp[i - 1] + a[i], a[i]). 증명은 a[i]가 음수,양수 나누어서 해보면 증명할 수 있음.

time complexity는 O(N)

int[] dp = new int[N];
dp[0]=a[0];
max_sum=a[0];
for(int i=1;i<N;i++){
	dp[i]=Math.max(dp[i-1]+a[i], a[i]);
	max_sum=Math.max(max_sum, dp[i]);
}

이때, memory optimization을 할 수 있다. dp[i]는 항상 dp[i-1]과 디펜던시가 있으니, 그 전단계를 가지고 있으면 O(N) 메모리를 O(1)으로 절약할 수 있다.

cur_max =a[0];
max_sum=a[0];
for(int i=1;i<N;i++){
	cur_max=Math.max(cur_max+a[i], a[i]);
	max_sum=Math.max(max_sum, dp[i]);
}

응용

위의 문제를 약간만 바꿔서 K보다 작으면서 가장 큰 값을 찾으라는 문제로 바뀌었다.

Given an array of integers A and an integer k, find a subarray that contains the largest sum, subject to a constraint that the sum is less than k?

intuition

안타깝게도 위의 제약조건이 들어가면 dp방식으로는 풀수 없다. 그리고 값을 비교해야 하기 때문에 sort가 필요하다. 그러면 O(longN)의 complexity가 붙겠지.

range sum은 보통 array의 처음부터 cumulative sum을 해서 cum[j]-cum[i] where i<j 을 해주면 구할 수 있다.

여기서 더 발전시키면, 왼쪽에서 부터 cum[j]를 TreeSet에 추가하기 전에, 트리에 이미있는 값들은 소트가 되어 있으므로 트리에 있는 값중 최적의 갑을 찾아낼 수 있다. 아래에서 cum[j],k는 상수 이므로 TreeSet의 값중에서 ceiling 를 찾으면 된다.

cum[j]-cum[i]<=k, where i cum[i]>=cum[j]-k

implementation

int maxSumLessThanK(int[] a, int k){
    int ret=Integer.MIN_VALUE;
    int sum=0;
    TreeSet<Integer> set = new TreeSet<>();
    set.add(0);
    for (int i = 0; i < N; i++){
        sum+=nums[i];
        int min = set.ceiling(sum-k);
        ret=Math.max(ret, min);        
        set.add(sum);
    }

    return ret;
}

Problems

알고리즘 이해가 되었다면 아래 문제들 풀어보시길.

• maximum subarray @leetcode

• maximum absolute difference between sum of two contiguous subarrays @geeks : Kadane 응용

• count of range sum @leetcode

Reference

• explanation @geeks