题目链接

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;}
}