【Leetcode】53.最大子數組（Maximum Subarray）

Leetcode - 53 Maximum Subarray (Easy)

題目描述：給定一個整數數組，求最大連續子數組的和。

解題思路：定義 dp[i] 為以第 i 個元素結尾的最大連續子數組之和。狀态轉移方程為 dp[i] = max(dp[i - 1] + nums[i], nums[i])。

public int maxSubArray(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int max = dp[0];
    for(int i = 1; i < nums.length; i++){
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        max = Math.max(max, dp[i]);
    }
    return max; 
}