道路標識-53.Maximum Subarray

質問する

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.

に答える

これは,与えられた配列の中で最も大きなサブ配列の和を求める問題である.そのために、以下の点を考えました.

サブアレイの和のみが要求されるので、インデックス0からnへの加算加算を適用する方式DPが決定される.

を求める最大値なので、前のインデックスの積算和が負数であれば加算しません.

コード#コード#

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        answer = nums[0]
        for i in range(1, len(nums)):
            nums[i] = max(nums[i], nums[i] + nums[i-1])
            answer = max(nums[i], answer)
        return answer