leetcode第53题

简介: 解法一和解法二的动态规划,只是在定义的时候一个表示以 i 开头的子数组,一个表示以 i 结尾的子数组,却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和,不如解法二直接,只保存最大的和。

image.png

给一个数组,找出一个连续的子数组,长度任意,和最大。

解法一 动态规划思路一

用一个二维数组 dp[ i ] [ len ] 表示从下标 i 开始,长度为 len 的子数组的元素和。

这样长度是 len + 1 的子数组就可以通过长度是 len 的子数组去求,也就是下边的递推式,

dp [ i ] [ len + 1 ] = dp[ i ] [ len ] + nums [ i + len - 1 ]。

当然,和第 5 题一样,考虑到求 i + 1 的情况的时候,我们只需要 i 时候的情况,所有我们其实没必要用一个二维数组,直接用一维数组就可以了。


publicintmaxSubArray(int[] nums) {
intn=nums.length;
int[] dp=newint[n];
intmax=Integer.MIN_VALUE;
for (intlen=1; len<=n; len++) {
for (inti=0; i<=n-len; i++) {
//直接覆盖掉前边对应的情况就行dp[i] =dp[i] +nums[i+len-1];
//更新 maxif (dp[i] >max) {
max=dp[i];
            }
        }
    }
returnmax;
}

时间复杂度:O(n²)。

空间复杂度:O(n)。

解法二 动态规划思路二

参考这里

用一个一维数组 dp [ i ] 表示以下标 i 结尾的子数组的元素的最大的和,也就是这个子数组最后一个元素是下边为 i 的元素,并且这个子数组是所有以 i 结尾的子数组中,和最大的。

这样的话就有两种情况,

  • 如果 dp [ i - 1 ] < 0,那么 dp [ i ] = nums [ i ]。
  • 如果 dp [ i - 1 ] >= 0,那么 dp [ i ] = dp [ i - 1 ] + nums [ i ]。
publicintmaxSubArray(int[] nums) {
intn=nums.length;
int[] dp=newint[n];
intmax=nums[0];
dp[0] =nums[0];
for (inti=1; i<n; i++) {
//两种情况更新 dp[i]if (dp[i-1] <0) {
dp[i] =nums[i];
        } else {
dp[i] =dp[i-1] +nums[i];
        }
//更新 maxmax=Math.max(max, dp[i]);
    }
returnmax;
}

时间复杂度: O(n)。

空间复杂度:O(n)。

解法一和解法二的动态规划,只是在定义的时候一个表示以 i 开头的子数组,一个表示以 i 结尾的子数组,却造成了时间复杂度的差异。问题就是解法一中求出了太多的没必要的和,不如解法二直接,只保存最大的和。


目录
打赏
0
0
0
0
10
分享
相关文章
|
9月前
leetcode-472. 连接词
leetcode-472. 连接词
67 0
|
9月前
|
leetcode:389. 找不同
leetcode:389. 找不同
40 0
|
9月前
leetcode-1219:黄金矿工
leetcode-1219:黄金矿工
92 0
顺手牵羊(LeetCode844.)
好多同学说这是双指针法,但是我认为叫它顺手牵羊法更合适
91 0
LeetCode 389. 找不同
给定两个字符串 s 和 t,它们只包含小写字母。
92 0
leetcode 283 移动零
leetcode 283 移动零
65 0
LeetCode 283. 移动零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
96 0
leetcode第42题
也就是红色区域中的水, 数组是 height = [ 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 ] 。 原则是高度小于 2,temp ++,高度大于等于 2,ans = ans + temp,temp = 0。 temp 初始化为 0 ,ans 此时等于 2。 height [ 0 ] 等于 0 < 2,不更新。 height [ 1 ] 等于 1 < 2,不更新。 height [ 2 ] 等于 0 < 2, 不更新。 height [ 3 ] 等于 2 >= 2, 开始更新 height [ 4 ] 等于 1 < 2,temp = temp + 1 = 1。 h
118 0
leetcode第42题
leetcode第12题
相当简洁了,主要就是把所有的组合列出来,因为罗马数字表示的大小就是把所有字母相加,所以每次 append 那个,再把对应的值减去就行了。 时间复杂度:不是很清楚,也许是 O(1)?因为似乎和问题规模没什么关系了。 空间复杂度:O(1)
leetcode第12题