[Leetcode] 53. Maximum Subarray
問題のショートカット
Time Complexity: O(n)
Space Complexity: O(1)
各最大部分と前の最大部分の和の結果を利用します.
配列の各インデックスには、自分の値と以前の最大部分とでより大きな値を選択するだけで最大のローカル値があります.つまり、前のインデックスの最大部分と負の値がある場合は、自分の値を選択できます.このプロセスにより,最終的には各インデックスで得られる最大部分の配列が得られる.
最大値は、すべての部分との最大値です.
リファレンス
Kadane's Algorithm - ブログ
Time Complexity: O(n)
Space Complexity: O(1)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxSubSum = subSumSoFar = nums[0]
for i in range(1, len(nums)):
# Initialize if the previous subsum is negative
if subSumSoFar < 0:
subSumSoFar = 0
subSumSoFar += nums[i]
if maxSubSum < subSumSoFar:
maxSubSum = subSumSoFar
return maxSubSumKadane's Algorithm
各最大部分と前の最大部分の和の結果を利用します.
配列の各インデックスには、自分の値と以前の最大部分とでより大きな値を選択するだけで最大のローカル値があります.つまり、前のインデックスの最大部分と負の値がある場合は、自分の値を選択できます.このプロセスにより,最終的には各インデックスで得られる最大部分の配列が得られる.
最大値は、すべての部分との最大値です.
リファレンス
Kadane's Algorithm - ブログ
Reference
この問題について([Leetcode] 53. Maximum Subarray), 我々は、より多くの情報をここで見つけました https://velog.io/@haebin/Leetcode-53.-Maximum-Subarrayテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol