[알고리즘] 카데인 알고리즘 Kadane's Algorithm

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

Maximum Subarray - LeetCode

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

---

*설명

정수로 이루어진 배열에서 연속된 부분 배열의 합의 최댓값을 반환하는 문제이다.

Brute force 론적으로 보면, for문을 두개 돌면서 O(n^2) 퍼포먼스가 나오는 방법을 떠올릴 수 있다. 하지만 O(n) 으로 접근하는 방법이 바로 카데인 알고리즘이다.

두 개의 정수형 변수가 사용된다.

 int maxSumEndingHere = 0;
 int maxSumSoFar = 0;

[ i..j ] 합이 음수이면, [ i..j+1 ] 합은 [ j+1 ]보다 작다. 이를 이용해 이전까지의 합을 무시하고 다시 더해가면서 현재까지의 최댓값을 비교하면 되는 알고리즘이다.

배열의 모든 값이 음수가 아니라는 가정에서 돌아간다. 

---

자바 코드

public void maxSubArraySum(int[] arr, int n){
    int maxSumSoFar = 0;
    int maxSumEndingHere = 0;

    for(int i = 0 ;i < n; i++){
    maxSumEndingHere +== arr[i]; //현재 값을 더한다. 

    if(maxSumEndingHere < 0)//누적합이 음수이면. 0으로 업데이트. 
    maxSumEndingHere = 0;

    if(maxSumSoFar < maxSumEndingHere )
    maxSumSoFar = maxSumEndingHere;

    }
    return maxSumSoFar;    
}