Leetcode 53. Maximum SubarrayJAVA語言

1

2

3

<code>Find the contiguous subarray within an array (containing at least one number) which has the largest sum.</code>

<code>For example, given the array [-2,1,-3,4,-1,2,1,-5,4],</code>

<code>the contiguous subarray [4,-1,2,1] has the largest sum = 6.</code>

題意：求連續子數組的最大和

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

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

<code>        </code><code>int</code> <code>len=nums.length;</code>

<code>        </code><code>if</code><code>(nums==</code><code>null</code> <code>|| len==</code><code>0</code><code>)</code><code>return</code> <code>0</code><code>;</code>

<code>         </code><code>int</code> <code>MAX=nums[</code><code>0</code><code>];</code>

<code>         </code><code>int</code> <code>curSum=nums[</code><code>0</code><code>];</code>

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

<code>             </code><code>if</code><code>(curSum&gt;</code><code>0</code><code>){</code>

<code>                 </code><code>curSum+=nums[i];</code>

<code>             </code><code>}</code><code>else</code><code>{</code>

<code>                 </code><code>curSum=nums[i];</code>

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

<code>             </code><code>MAX=Math.max(curSum,MAX);</code>

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

<code>         </code><code>return</code> <code>MAX;</code>

<code>        </code> 

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

<code>}</code>

PS:第一種思路，逐漸累加循環。

還有一種思路，可以用動态規劃做。

19

<code>        </code><code>//dp[i]代表以nums[i]為結尾的最大和。</code>

<code>        </code><code>int</code><code>[] dp=</code><code>new</code> <code>int</code><code>[len];</code>

<code>        </code><code>dp[</code><code>0</code><code>]=nums[</code><code>0</code><code>];</code>

<code>        </code><code>int</code> <code>MAX=dp[</code><code>0</code><code>];</code>

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

<code>            </code><code>if</code><code>(dp[i-</code><code>1</code><code>]&lt;</code><code>0</code><code>){</code>

<code>                </code><code>dp[i]=nums[i];</code>

<code>            </code><code>}</code><code>else</code><code>{</code>

<code>                </code><code>dp[i]=dp[i-</code><code>1</code><code>]+nums[i];</code>

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

<code>            </code><code>MAX=Math.max(dp[i],MAX);</code>

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

<code>        </code><code>return</code> <code>MAX;</code>

本文轉自 努力的C 51CTO部落格，原文連結:http://blog.51cto.com/fulin0532/1905435