lintcode 最大子數組III

　　給定一個整數數組和一個整數 k，找出 k 個不重疊子數組使得它們的和最大。每個子數組的數字在數組中的位置應該是連續的。

　　傳回最大的和。

　　子數組最少包含一個數

　　給出數組 <code>[-1,4,-2,3,-2,3]</code> 以及 k = <code>2</code>，傳回 <code>8</code>

　　dp[i][j] = max(dp[x][j-1]+maxs[x+1][i])

　　dp[i][j] 表示前 i 個數中 j 個子數組的最大值，

　　maxs[i][j] 表示 第i個數到第j個數中最大子數組的和。

<code>public</code> <code>class</code> <code>Solution {</code>

<code>    </code><code>/**</code>

<code>     </code><code>* @param nums: A list of integers</code>

<code>     </code><code>* @param k: An integer denote to find k non-overlapping subarrays</code>

<code>     </code><code>* @return: An integer denote the sum of max k non-overlapping subarrays</code>

<code>     </code><code>*/</code>

<code>    </code><code>public</code> <code>int</code> <code>maxSubArray(</code><code>int</code><code>[] nums, </code><code>int</code> <code>k) {</code>

<code>        </code><code>// write your code here</code>

<code>        </code><code>int</code><code>[][] maxs = </code><code>new</code> <code>int</code><code>[nums.length][nums.length];</code>

<code>        </code><code>int</code><code>[][] dp = </code><code>new</code> <code>int</code><code>[nums.length][k+</code><code>1</code><code>];</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>; i&lt;nums.length; ++i) {</code>

<code>            </code><code>for</code><code>(</code><code>int</code> <code>j=i; j&lt;nums.length; ++j) {</code>

<code>                </code><code>maxs[i][j] = maxSum(nums, i, j);</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>        </code> 

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>0</code><code>; i&lt;dp.length; ++i) {</code>

<code>            </code><code>for</code><code>(</code><code>int</code> <code>j=</code><code>0</code><code>; j&lt;dp[i].length; ++j) {</code>

<code>                </code><code>dp[i][j] = Integer.MIN_VALUE;</code>

<code>            </code><code>dp[i][</code><code>1</code><code>] = maxs[</code><code>0</code><code>][i];</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>i=</code><code>1</code><code>; i&lt;nums.length; ++i) {</code>

<code>            </code><code>for</code><code>(</code><code>int</code> <code>j=</code><code>2</code><code>; j&lt;=k; ++j) {</code>

<code>                </code><code>for</code><code>(</code><code>int</code> <code>x=j-</code><code>2</code><code>; x&lt;i; ++x) {</code>

<code>                    </code><code>dp[i][j] = Math.max(dp[i][j], dp[x][j-</code><code>1</code><code>] + maxs[x+</code><code>1</code><code>][i]);</code>

<code>                </code><code>}</code>

<code>        </code><code>return</code> <code>dp[nums.length-</code><code>1</code><code>][k];</code>

<code>    </code><code>}</code>

<code>    </code><code>private</code> <code>int</code> <code>maxSum(</code><code>int</code><code>[] nums, </code><code>int</code> <code>i, </code><code>int</code> <code>j) {</code>

<code>        </code><code>int</code> <code>sum = </code><code>0</code><code>, maxs = Integer.MIN_VALUE;</code>

<code>        </code><code>for</code><code>(</code><code>int</code> <code>x = i; x &lt;= j; ++x) {</code>

<code>            </code><code>sum += nums[x];</code>

<code>            </code><code>if</code> <code>(maxs &lt; sum) {</code>

<code>                </code><code>maxs = sum;</code>

<code>            </code><code>if</code> <code>(sum &lt; </code><code>0</code><code>) {</code>

<code>                </code><code>sum = </code><code>0</code><code>;</code>

<code>        </code><code>return</code> <code>maxs;</code>

<code>}</code>

本文轉自 小眼兒 部落格園部落格，原文連結：http://www.cnblogs.com/hujunzheng/p/7376237.html，如需轉載請自行聯系原作者