[LeetCode] 最大连续子序列和或者乘积,以及最长连续子串
[LeetCode] 最大连续子序列和或者乘积,以及最长连续子串
Finley.Hamilton 发表于3年前
[LeetCode] 最大连续子序列和或者乘积,以及最长连续子串
  • 发表于 3年前
  • 阅读 532
  • 收藏 5
  • 点赞 0
  • 评论 2

【腾讯云】新注册用户域名抢购1元起>>>   

摘要: 最大连续自序列的问题困扰我多年,网上大部分都是只贴代码

#题目

Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

思路

其实不管是最大连续自序列和还是乘积,关键的一个概念是定义一个变量叫做 “包含当前值的最大连续序列值(和/乘积)”,举例来说curMax

这个值的存在使得包含下一个位置的最大连续序列值的求解成为可能,以最大连续自序列求和为例,

curMax(x+1) = max(A[x+1], curMax(x) + A[X])

对于最大连续自序列乘积,需要纪录两个,一个是包含当前值的最大连续子序列乘积, 一个是包含当前值的最小自序列乘积

curMax(x + 1) = Math.max(curMax(x)*A[x], curMin(x)*A[x], A[x]) curMin(x + 1) = Math.min(curMax(x)*A[x], curMin(x)*A[x], A[x])

因为包含当前值的最大值(最小值)只能由这三种可能构成

代码

最大连续自序列和

public class Solution {
    public int maxSubArray(int[] A) {
        int curMax = A[0];
        int max = A[0];
        for (int i = 1; i < A.length ; i++) {
            curMax = Math.max(A[i], curMax + A[i]);
            max = Math.max(max, curMax);
        }
        return max;
    }
}

最大连续子序列乘积

public class MaxProductSubArray {

    public int maxProduct(int[] A) {
        int curMax = A[0];
        int curMin = A[0];
        int max = A[0];

        for(int i = 1; i < A.length; i++) {
            // 注意这里先存起来,下面要在更新之后再用一次
            int temp = curMax * A[i];
            curMax = Math.max(A[i], Math.max(curMax * A[i], curMin * A[i]));
            curMin = Math.min(A[i], Math.min(temp, curMin * A[i]));
            max = Math.max(curMax, max);
        }

        return max;
    }
}

最长连续子串的想法

d[i][j]表示A[0...i],B[0...j],并且以A[i]和B[j]结尾的最长公共连续子串的长度

d[i][j] = d[i-1][j-1] if A[i] == B[j] d[i][j] = 0 if A[i] != B[j]

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
Finley.Hamilton
粉丝 4
博文 44
码字总数 15431
评论 (2)
liqiang1226
没看太明白,是dp吗?
Finley.Hamilton

引用来自“liqiang1226”的评论

没看太明白,是dp吗?
严格来说可以算DP,但是事实上下一个结果可以由前一个结果直接得出而不需要援引更多之前结果
×
Finley.Hamilton
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: