LeetCode - Maximum Subarray



質問する


リンクテキスト
海外で何回も解决されていると闻いたので、Easy段阶の问题を解いてみました.これは,最大部分の統合問題が,資料構造課で学んだ問題である.

コード#コード#

class Solution:
    def maxSubArray(self, nums:list) -> int:
        mxSum = 0
        sum = 0
        for i in nums:
            if sum+i > 0:
                sum += i
            else:
                sum = 0
            mxSum = max(mxSum, sum)
        if mxSum == 0:
            return max(nums)

        return mxSum

ツリーコードは、classをコミットしてメソッドを実装する方法です.配列に[2,1,3,4,1,2,1,-5,4]が与えられた場合、コードは以下のように動作する.
  • 積算値とinsumとiの2番目の値の和が負でない場合は、続行します.
  • sum+iが0以下である場合、sumは0に初期化される.
  • サイクルが終了するたびに、mxSumには、mxSumの現在値と和の値のうちの1つの大きな値が格納される.
  • これにより,連続部分集合における最大値をO(n)の時間内に達成できた.しかし、与えられた配列が負の値のみからなる配列である場合、ex)[2,−1,3]の負の値の最大値を返すことによって解決される.