題目鏈接

53. 最大子數組和 - 力扣（LeetCode）

題目解析

算法原理

解法1: 暴力(一個循環用來固定,一個用來找最大的子數組O(n^2),每次往后拓展一個元素就判斷是否是最長的),枚舉出每一種情況, 然后不斷更新最大的

解法二: dp

1> dp的含義: dp[i]記錄的是以nums[i]為結尾的最大連續子數列和?

2> 遞推公式: 1) 延續前面的計算出來的子序列和繼續累加 dp[i]= nums[i]+dp[i-1]

? ? ? ? ? ? ? ? ? ? ? 2) 沒有延續, 直接以自身為起點 dp[i] = nums[i]

? ? ? ? ? ? ? ? ? ? ? 得出遞推公式:? dp[i]=max(nums[i]+dp[i-1],nums[i])

3> 確定源頭: dp[0]=nums[0]; 就是數組的第一個元素

代碼編寫

解法一: 會超時, 只能過大部分的測試用例

class Solution {public int maxSubArray(int[] nums) {// 暴力int max = Integer.MIN_VALUE;for (int i = 0; i < nums.length; i++) {int tmp = nums[i];max = Math.max(tmp, max);for (int j = i + 1; j < nums.length; j++) {tmp += nums[j];// 每次加一個數就計算最大值max = Math.max(tmp, max);}}// 把找到的最大值返回return max;}
}

dp數組

class Solution {public int maxSubArray(int[] nums) {// 動態規劃// 源int max = nums[0];// 初始化數組的第一個元素int dp = nums[0];// 當前子數組的和for (int i = 1; i < nums.length; i++) {dp = Math.max(nums[i], dp + nums[i]);// 計算子數組max = Math.max(max, dp);// 更新最大子數組的和}return max;}
}

?