Maximum Subarray

문제

정수 배열 nums가 주어질 때, 연속된 부분 배열(Subarray) 중 그 합이 가장 큰 부분 배열을 찾아 그 합을 반환하는 프로그램을 작성하는 문제입니다.

• 입력: 정수 배열 nums (1 <= nums.length <= 10^5)
• 출력: 연속된 부분 배열의 최대 합

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

풀이: DP 탐색

배열을 한 번 순회하면서 연속된 구간의 합을 추적합니다.

• 상태 정의: 1차원 배열 d[i]를 i번째 원소를 마지막으로 하는 연속 부분 배열의 최대 합으로 정의합니다.
• 초기화: 첫 번째 원소는 그 자체로 부분 배열이 되므로 d[0] = nums[0]으로 초기화하고, 전체 최댓값 ans도 d[0]으로 설정합니다.
• 점화식 도출: i번째 원소에서 선택할 수 있는 경우는 두 가지입니다.
  1. 이전까지의 연속된 합에 현재 원소를 더해 구간을 연장하는 경우 (d[i - 1] + nums[i])
  2. 이전 구간을 과감히 버리고, 현재 원소부터 새롭게 연속 구간을 시작하는 경우 (nums[i]) 따라서 점화식은 d[i] = Math.max(d[i - 1] + nums[i], nums[i]) 가 됩니다.
• 최댓값 갱신: 배열을 순회하며 d[i]를 구할 때마다 전체 최댓값 ans를 갱신합니다.

코드

class Solution {
    public int maxSubArray(int[] nums) {
        int[] d = new int[nums.length];

        d[0] = nums[0];
        int ans = d[0];
        for (int i = 1; i < nums.length; i++) {
            d[i] = Math.max(d[i - 1] + nums[i], nums[i]);
            ans = Math.max(ans, d[i]);
        }

        return ans;
    }
}

알고리즘 분류

다이나믹 프로그래밍 (Dynamic Programming)