溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
【題目描述】
Given an array of integers, find two non-overlapping subarrays which have the largest sum.The number in each subarray should be contiguous.Return the largest sum.
Notice:The subarray should contain at least one number
給定一個整數數組，找出兩個 不重疊 子數組使得它們的和最大。每個子數組的數字在數組中的位置應該是連續的。返回最大的和。
注意:子數組最少包含一個數
【題目鏈接】
http://www.lintcode.com/en/problem/maximum-subarray-ii/
【題目解析】
嚴格來講這道題這道題也可以不用動規來做，這里還是采用經典的動規解法。Maximum Subarray 中要求的是數組中最大子數組和，這里是求不相重疊的兩個子數組和的和最大值，做過買賣股票系列的題的話這道題就非常容易了，既然我們已經求出了單一子數組的最大和，那么我們使用隔板法將數組一分為二，分別求這兩段的最大子數組和，求相加后的最大值即為最終結果。隔板前半部分的最大子數組和很容易求得，但是后半部分難道需要將索引從0開始依次計算嗎？NO!!! 我們可以采用從后往前的方式進行遍歷，這樣時間復雜度就大大降低了。
源碼分析:前向搜索和逆向搜索我們使用私有方法實現，可讀性更高。注意是求非重疊子數組和，故求maxTwoSub時i 的范圍為0, size - 2, 前向數組索引為 i, 后向索引為 i + 1.
復雜度分析:前向和后向搜索求得最大子數組和，時間復雜度 O(2n)=O(n)O(2n)=O(n)O(2n)=O(n), 空間復雜度 O(n)O(n)O(n). 遍歷子數組和的數組求最終兩個子數組和的最大值，時間復雜度 O(n)O(n)O(n). 故總的時間復雜度為 O(n)O(n)O(n), 空間復雜度 O(n)O(n)O(n).
【參考答案】
http://www.jiuzhang.com/solutions/maximum-subarray-ii/
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
