[LeetCode] 53. Maximum Subarray - Java

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

Maximum Subarray - LeetCode

---

문제

Given an integer array nums, find the subarray which has the largest sum and return its sum.

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

---

풀이

풀이 과정

주어진 배열에서 가장 큰 부분배열의 합을 구하는 문제이다.

배열의 2번째 인덱스 부터 탐색하며 각 인덱스별 최대 부분배열의 합을 구하여 memoization한다. 
첫 번째 인덱스는 항상 그 자체로 최대 부분배열의 합이므로 건너뛰고 시작한다.

현재 인덱스의 부분배열의 최대 합은 이전 인덱스의 최대 부분배열 합에 현재 인덱스를 더한 값과 현재 인덱스의 값중 큰 값이 되고, 이 때 구한 최대 부분배열 합이 지금 까지의 부분배열의 합 중 가장 큰 값이라면 최대값을 갱신한다

int maxSum = nums[0]; // 가장 큰 부분 배열의 합

for(int i = 1; i < nums.length; i++){
    /*
     * 현재 인덱스의 최대 부분합
     *
     * 이전 인덱스의 최대 부분합에서 현재 인덱스를 더한 값과 
     * 현재 인덱스의 값중 큰 값이 현재 인덱스의 최대 부분합
     */
    nums[i] = Math.max(nums[i - 1] + nums[i], nums[i]);
    maxSum = Math.max(maxSum, nums[i]); // 가장 큰 부분 배열의 합 갱신
}

 

최종적으로 구한 최대값을 return 한다.

return maxSum;

---

최종 코드

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0]; // 가장 큰 부분 배열의 합

        for(int i = 1; i < nums.length; i++){
            /*
             * 현재 인덱스의 최대 부분합
             *
             * 이전 인덱스의 최대 부분합에서 현재 인덱스를 더한 값과 
             * 현재 인덱스의 값중 큰 값이 현재 인덱스의 최대 부분합
             */
            nums[i] = Math.max(nums[i - 1] + nums[i], nums[i]);
            maxSum = Math.max(maxSum, nums[i]); // 가장 큰 부분 배열의 합 갱신
        }

        return maxSum;
    }
}

---