[Misc][Medium] 53. Maximum Subarray

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

 

Q. 주어진 숫자배열의 최대 부분합을 구하라. 

 

 

Solution. 

 2 중 loop를 돌면 풀이는 간단해 진다. 

 하지만, O(N)에 구할 방법을 고민해 보자. 

 

 여기서 잘 알려진 알고리즘이 dynamic programming을 활용한, 방법이다. 

 즉, 이전까지의 부분합의 최대값에 현재위치값을 더한 최대값이 현재의 최대 부분합이 된다는 것이다. 

 

 이것을 Kadane's Algorithm이라 하며, 이 알고리즘은 꽤 유명하다. 

 

 이것을 토대로 코드를 만들어 본다. 

 

 

public int MaxSubArray(int[] nums) 
{
    // 주어진 배열에서 최대의 합을 가진 subArray를 찾고 그 최대합을 반환하라.

    // Kadane's Algorithm.
    int maxV = int.MinValue;
    int sum = 0;
    for(int q = 0; q < nums.Length; ++q)
    {
        sum = Math.Max(nums[q], sum+nums[q]);
        maxV = Math.Max(sum, maxV);
    }
    return maxV;
}

 

적당한 결과. 

 

Note : 관련 문제를 조금 더 풀어봐야 할 필요를 느낀다.

 

references : https://honeywater97.tistory.com/100