今天打算多做一题。
1、题目描述
2、逻辑分析
哈哈,这题我前两天在小红书刷到了,博主答不上来,一样的是,我也不知道怎么做。当时只看到评论说什么dp解法,看看题解怎么说。现在才反应过来dp = dynamic programming ,题解给出了两种解题思路:动态规划和分治,先从动态规划开始:
直接代码说明
3、代码演示
public int maxSubArray(int[] nums) {
// start 变量用于记录以当前遍历到的元素为结尾的子数组的最大和
int start = 0, maxRes = nums[0];
// 遍历数组中的每一个元素 x
for(int x : nums){
// 对于每一个元素 x,我们有两种选择:
// 1. 以 x 开头,形成一个新的子数组(此时子数组和为 x)
// 2. 将 x 加入到之前的子数组中(此时子数组和为 pre + x)
// 我们选择两者中较大的那个作为当前的最大子数组和 pre
start = Math.max(start + x, x);
// 同时,我们还需要将 pre 与迄今为止找到的最大子数组和 maxAns 进行比较
// 如果 pre 更大,那么更新 maxAns
maxRes = Math.max(maxRes, start);
}
// 返回迄今为止找到的最大子数组和
return maxRes;
}
真的是妙极了,简短的代码蕴含了dp思想。时间复杂度;O(n),空间复杂度:O(1)。
start = Math.max(start + x, x);在评论区看到了对这句核心代码的明了阐述如下:
如果前边累加后还不如自己本身大,那就把前边的都扔掉,从此自己本身重新开始累加。
分治算法看不太懂,沉不下心来看,先放放吧,再见啦!