Leetcode日記_01,乘積最大子序列

justjavac 發布于2019-07-31 10:36 / 2162人閱讀

摘要：題目乘積最大子序列給定一個整數數組，找出一個序列中乘積最大的連續子序列該序列至少包含一個數。示例輸入輸出解釋結果不能為因為不是子數組。當大于時如果，，如果，，時間復雜度和空間復雜度均為，其中是數組中的元素個數。動態規劃法參考自

題目 乘積最大子序列

給定一個整數數組 nums ，找出一個序列中乘積最大的連續子序列（該序列至少包含一個數）。

示例 1:

輸入: [2,3,-2,4]
輸出: 6
解釋: 子數組 [2,3] 有最大乘積 6。
示例 2:

輸入: [-2,0,-1]
輸出: 0
解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。

我的解題思路 暴力法

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

執行代碼 OK通過
我們再自行測試一遍
先將測試用例改為[-2], OK也沒問題
如果測試用例非常長,那么該方法肯定不可取,因為其時間復雜度為O(n^2)

leetcode上的范例

class Solution:
    def maxProduct(self, nums: list) -> int:
        B = nums[::-1]
        for i in range(1, len(nums)):
            nums[i] *= nums[i - 1] or 1
            B[i] *= B[i - 1] or 1
        return max(max(nums), max(B))

這個方法我有點搞不明白
按理來說設nums中元素個數為x,則理論上應該有

$$ sum_{i=1}^x x = frac{1}{2} x^2 + frac{1}{2} x $$

個非空子序列,而上面這個方法中nums和B僅列出了x+x=2x個非空子序列

動態規劃

狀態定義：
f(x) -------- nums數組中[0, x]范圍內的最大連續子序列的乘積，且該連續子序列以nums[x]結尾
g(x)?-------- nums數組中[0, x]范圍內的最小連續子序列的乘積，且該連續子序列以nums[x]結尾
狀態轉移：
（1）當x等于0時，顯然此時[0, x]范圍內只有一個元素，f(0)和g(0)均等于這個唯一的元素。
（2）當x大于0時
a：如果nums[x] >= 0，f(x) = max(f(x - 1)  nums[x], nums[x])，g(x) = min(g(x - 1)  nums[x], nums[x])
b：如果nums[x] < 0，f(x) = max(g(x - 1)  nums[x], nums[x])，g(x) = min(f(x - 1)  nums[x], nums[x])
時間復雜度和空間復雜度均為O(n)，其中n是nums數組中的元素個數。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxpd = []
        minpd = []
        for i in range(len(nums)):
            if i == 0:
                maxpd.append(nums[0])
                minpd.append(nums[0])
            else:
                if nums[i] >= 0:
                    maxpd.append(max(maxpd[i-1]*nums[i], nums[i]))
                    minpd.append(min(minpd[i-1]*nums[i], nums[i]))
                else:
                    maxpd.append(max(minpd[i-1]*nums[i], nums[i]))
                    minpd.append(min(maxpd[i-1]*nums[i], nums[i]))
        return max(maxpd)

動態規劃法參考自https://blog.csdn.net/qq_4123...

GPU云服務器云服務器最大子序列 leetcode_35_SearchIn 最長遞增子序列最長公共子序列

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/44090.html

leetcode152 Maximum Product Subarray

摘要：題目要求從一個整數數組中找到一個子數組，該子數組中的所有元素的乘積最大。比如數組的最大乘積子數組為思路與代碼這題目考察了動態編程的思想。至于為什么還要比較，是因為如果是一個負數的，那么之前的最小乘積在這里可能就成為了最大的乘積了。題目要求 Find the contiguous subarray within an array (containing at least one num...

Arno 2019-08-16 10:57 評論0 收藏0
小李飛刀：做題第八彈！

摘要：認真做題的分割線第一題乘積最大子序列難度中等給定一個整數數組，找出一個序列中乘積最大的連續子序列該序列至少包含一個數。寫在前面的話慢慢轉變思路，不再死磕不會做的題，思路可以先借鑒，但是一定要吃透透。上周末看完看完了《算法圖解》，感覺對一些題目的思路有比較大的幫助，但是還是要在實踐中理解。認真做題的分割線第一題 152. 乘積最大子序列難度：中等給定一個整數數組nums，找出一個...

ztyzz 2019-07-31 10:11 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 343. Integer Break

摘要：思路動態規劃，前五個數的最大乘積為，后面的第個數的最大乘積，由從后往前數包括本身的第三個數乘以得到。何睿何睿前個數的最大乘積動態規劃第個數的最大乘積為往前數第三個數思路與上面的思路一致，優化了空間源代碼文件在這里。 Description Given a positive integer n, break it into the sum of at least two positive...

ckllj 2019-07-31 10:17 評論0 收藏0
leetcode-300-Longest Increasing Subsequence

摘要：本質找出最長的遞增子序列的長度，可以是不連續的。應用判斷滿足一定條件的子序列的最大長度，用動態數組加以處理。二分法確定滿足條件的位置。類似二分法查找元素，查找某種情況的子序列。本質：找出最長的遞增子序列的長度，可以是不連續的。用一個數組存儲遞增子序列，遍歷原始數組，每增加一個數，往里添加到對應的順序，記錄他的位置，即為此數組的長度。成立的理由：每一個數添加以后，都有對...

amc 2019-07-30 17:36 評論0 收藏0