Lintcode42 Maximum Subarray II solution 題解

【題目描述】

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

給定一個(gè)整數(shù)數(shù)組，找出兩個(gè) 不重疊 子數(shù)組使得它們的和最大。每個(gè)子數(shù)組的數(shù)字在數(shù)組中的位置應(yīng)該是連續(xù)的。返回最大的和。

注意:子數(shù)組最少包含一個(gè)數(shù)

【題目鏈接】

http://www.lintcode.com/en/problem/maximum-subarray-ii/

【題目解析】

嚴(yán)格來講這道題這道題也可以不用動(dòng)規(guī)來做，這里還是采用經(jīng)典的動(dòng)規(guī)解法。Maximum Subarray 中要求的是數(shù)組中最大子數(shù)組和，這里是求不相重疊的兩個(gè)子數(shù)組和的和最大值，做過買賣股票系列的題的話這道題就非常容易了，既然我們已經(jīng)求出了單一子數(shù)組的最大和，那么我們使用隔板法將數(shù)組一分為二，分別求這兩段的最大子數(shù)組和，求相加后的最大值即為最終結(jié)果。隔板前半部分的最大子數(shù)組和很容易求得，但是后半部分難道需要將索引從0開始依次計(jì)算嗎？NO!!! 我們可以采用從后往前的方式進(jìn)行遍歷，這樣時(shí)間復(fù)雜度就大大降低了。

源碼分析:前向搜索和逆向搜索我們使用私有方法實(shí)現(xiàn)，可讀性更高。注意是求非重疊子數(shù)組和，故求maxTwoSub時(shí)i 的范圍為0, size - 2, 前向數(shù)組索引為 i, 后向索引為 i + 1.

復(fù)雜度分析:前向和后向搜索求得最大子數(shù)組和，時(shí)間復(fù)雜度 O(2n)=O(n)O(2n)=O(n)O(2n)=O(n), 空間復(fù)雜度 O(n)O(n)O(n). 遍歷子數(shù)組和的數(shù)組求最終兩個(gè)子數(shù)組和的最大值，時(shí)間復(fù)雜度 O(n)O(n)O(n). 故總的時(shí)間復(fù)雜度為 O(n)O(n)O(n), 空間復(fù)雜度 O(n)O(n)O(n).

【參考答案】

http://www.jiuzhang.com/solutions/maximum-subarray-ii/