【題目描述】
Given an array of integers and a number k, find k 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ù) k，找出 k 個(gè)不重疊子數(shù)組使得它們的和最大。每個(gè)子數(shù)組的數(shù)字在數(shù)組中的位置應(yīng)該是連續(xù)的。返回最大的和。
注意:子數(shù)組最少包含一個(gè)數(shù)
【題目鏈接】
http://www.lintcode.com/en/problem/maximum-subarray-iii/
【題目解析】
最重要的思路：
維護(hù)一個(gè) globalMax [ k+1 ] [ len+1 ] 的矩陣， globalMax [ i ] [ j ] ?代表了前 j 個(gè)數(shù)中取 i 個(gè) subarray 得到的最大和， 注意這里第 j 個(gè)數(shù)不一定被包括。
一個(gè) int 類(lèi)型: localMax, 每次寫(xiě)第 globalMax 的 第 i 行 第 j 列時(shí)用到的， 記錄前 j 個(gè)數(shù)中取 i 個(gè) subarray 得到的最大和， 但包括第 j 個(gè)數(shù)。
【參考答案】
