題目

  • 題目連結
  • 目標函式 : maxSubArray(nums)
    • Input : nums: List[int]
    • Output : int

解題概念

  • 題意 : 給定一整數陣列 nums，找出擁有最大總和的 Subarray，並將該總和回傳
  • Subarray 定義 : 一陣列中連續非空的元素序列

我的寫法

  • 想法 : 使用 Dynamic Programming 中的 Kadane’s Algorithm
    • 變數 :
      • round_max : 紀錄當前回合的總和最大值
      • result_max : 紀錄目前比較過之回合的最大值
    • 每回合要做的事 :
      1. 更新 round_max : 需要去判斷 num 是否要加入到 Subarray 中
        • 方式 : 比較 num 與 (round_max + num) 的大小，並將較大者更新到 round_max 中
      2. 更新 result_max : 比較 round_max 與 result_max 的大小，並將較大者更新到 result_max 中
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    def maxSubArray(self, nums):
        
        round_max = 0
        result_max = -10 ** 4 - 1
        for num in nums:
            round_max = max(round_max + num, num)
            result_max = max(result_max, round_max)
        return result_max
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 567 ms (faster than 75.86%)
    • Memory Usage: 26.2 MB (more than 86.7%)

解答 or 其他優秀寫法

  • 想法 : 與我想法類似