iT邦幫忙

2021 iThome 鐵人賽

DAY 17
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 17

【第十七天 - 動態規劃 題目分析】

  • 先簡單回顧一下,今天預計分析的題目: 53. Maximum Subarray

  • 題目敘述:https://leetcode.com/problems/maximum-subarray/

  • 題目敘述:

    • 題目會給一個 nums 的 list,需要找出至少一個數字的連續值,他們相加的結果會是最大的
      https://ithelp.ithome.com.tw/upload/images/20210917/20140592E6ivIYKvgn.png
  • 測資的 Input/Output

    • 會給一個 nums 的 list,需要回傳連續相加最大的值
      https://ithelp.ithome.com.tw/upload/images/20210917/20140592lOctlMrk8E.png
  • 這種題目「暴力的解法」就是把每個相加的值儲存起來,找出最大的值 (max)
    https://ithelp.ithome.com.tw/upload/images/20210917/201405929iTuDFC9xl.png

  • 若有N筆資料,那暴力解法的

    • 時間成本:需要兩個迴圈,大約 O(N^2)
    • 空間成本:需要 N*N 的空間
  • 由於他是要算最佳解,我們只要記錄 max 即可

    • 我們從第2個位置( index = 1 )開始讀取 nums
      • 若前一個位置大於 0 (才有累加的價值),就將此位置+前一個位置的值
      • 若前一個位置小於等於 0 (沒有必要累加),就不用理他,此位置就保持原狀
        https://ithelp.ithome.com.tw/upload/images/20210917/20140592N6knHzzi4E.png
  • python 實作

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

上一篇
【第十六天 - 動態規劃 介紹】
下一篇
【第十八天 - Binary Tree介紹】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言