(Python, Java) 리트코드 - Maximum Subarray

15 Apr 2022 in Algorithm on Leetcode

[문제 링크]

Python 풀이

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for idx in range(1, len(nums)):
            nums[idx] += nums[idx - 1] if nums[idx - 1] >= 0 else 0

        return max(nums)

Java 풀이

import java.util.Arrays;

class Solution {
    public int maxSubArray(int[] nums) {
        for (int idx = 1; idx < nums.length; idx++) {
            nums[idx] += nums[idx - 1] >= 0 ? nums[idx - 1] : 0;
        }
        return Arrays.stream(nums).max().getAsInt();
    }
}

메모이제이션 누적으로 풀 수 있다.
이전 값이 음수라면 현재 인덱스부터 다시 누적하면 되므로 0을 더해주도록 한다.