Python:アルゴリズム(Letcode maxSubArray)

Q.数値リストnumsをパラメータとすると、どの連続要素を追加したときに最大値が得られますか?一番大きい値段を探して帰ってください.

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
설명: [4,-1,2,1] 를 더하면 6이 가장 크기 때문

モデル解答1

max so fat,cur so farは負無限大(-float('inf'))に割り当てられる.

配列の要素数に従って遍歴し、cur so farにiの2番目の要素を追加します.

curr so farvs.i要素を比較して、より大きな数を割り当てる.この過程がなければ,cur so farは音の無限大から抜け出すことができない.

max so farはcur so farに比べてより大きな数を割り当てる.

def maxSubArray(nums):
    max_so_far = curr_so_far = -float('inf')
    for i in range(len(nums)):
        curr_so_far += nums[i] # Add curr number
        #print('1',curr_so_far)
        curr_so_far = max(curr_so_far, nums[i]) # Check if should abandon accumulated value so far if it's a burden due to negative value accumulated
        #print('2',curr_so_far)
        max_so_far = max(max_so_far, curr_so_far) # Update answer
        #print('3',max_so_far)
    return max_so_far
print(maxSubArray([-2,1, 3, 4, -3, 3]))

モデル解答2
arrayの要素は最初から回転します.
i-1要素が0より大きい場合にのみ、iの1番目の要素に追加されます.
このようにして、ドアをノックした後、最大の数字を返します.

def maxSubArray(nums):
    for i in range(1, len(nums)):
        if nums[i-1] > 0:
            nums[i] += nums[i-1] 
            print(nums)
    return max(nums)