文档章节

[LeetCode] 最大连续子序列和或者乘积,以及最长连续子串

Finley.Hamilton
 Finley.Hamilton
发布于 2014/11/08 09:39
字数 491
阅读 614
收藏 5

#题目

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

Finley.Hamilton

粉丝 5
博文 45
码字总数 15431
作品 0
广州
加载中

评论(2)

Finley.Hamilton
Finley.Hamilton

引用来自“liqiang1226”的评论

没看太明白,是dp吗?
严格来说可以算DP,但是事实上下一个结果可以由前一个结果直接得出而不需要援引更多之前结果
liqiang1226
liqiang1226
没看太明白,是dp吗?
动态规划

动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长非降子序列(LIS) 最大乘积子串 Unique Paths Unique Paths II Minimum Path Sum Triangle 最...

廖少少
2017/09/27
0
0
动态规划算法之:最长公共子序列 & 最长公共子串(LCS)

1、先科普下最长公共子序列 & 最长公共子串的区别: 找两个字符串的最长公共子串,这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、最长公共子串 其实这是一个序贯决...

大数据之路
2013/03/25
0
2
[算法总结] 13 道题搞定 BAT 面试——字符串

本文首发于我的个人博客:尾尾部落 1. KMP 算法 谈到字符串问题,不得不提的就是 KMP 算法,它是用来解决字符串查找的问题,可以在一个字符串(S)中查找一个子串(W)出现的位置。KMP 算法把...

繁著
09/05
0
0
删除部分字符使其变成回文串问题——最长公共子序列LCS问题

先要搞明白:最长公共子串和最长公共子序列的区别。 最长公共子串(Longest Common Substirng):连续 最长公共子序列(Longest Common Subsequence,LCS):不必连续 题目:给定一个字符串s...

牧师-Panda
2016/09/10
73
0
《程序员代码面试指南》Python实现(个人读书笔记)

说明   最近一直在读左神的书——《程序员代码面试指南—IT名企算法与数据结构题目最优解》,为了记录自己的学习成果,并且方便以后查看,将自己读书时的想法与使用python实现的代码记录在...

qq_34342154
2017/09/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

MySQL 到底支不支持事务嵌套?

最近开发中遇到了使用MySQL,多次开启事务,出现了数据错乱问题,伪代码如下: begin; # 操作1 begin; # 操作2 rollback; 执行完后出现了操作1的数据真正写入,只有操作2的数据回滚...

宇润
27分钟前
3
0
fastDfs应用(安装过程待写)

1.效果 2.安装 2.1 导入已经安装好fastDFS的镜像 2.1.1 导入镜像 2.1.2 更改系统兼容性 2.1.3 开机 2.1.4 修改 一下内容 2.1.4.1 修改系统的ip 原来系统ip...

Lucky_Me
31分钟前
3
0
5. Python3源码—字符串(str)对象

5.1. 字符串对象 字符串对象是“变长对象”。 5.1.1. Python中的创建 Python中字符串(strs)对象最重要的创建方法为PyUnicode_DecodeUTF8Stateful,如下Python语句最终会调用到PyUnicode_D...

Mr_zebra
50分钟前
3
0
第十章:路由网关(Zuul)进阶:过滤器、异常处理

第十章:路由网关(Zuul)进阶:过滤器、异常处理 简单介绍了关于Zuul的一些简单使用以及一些路由规则的简单说明。而对于一个统一网关而言,需要处理各种各类的请求,对不同的url进行拦截,或者...

DemonsI
52分钟前
2
0
nginx屏蔽指定接口(URL)

Step1:需求 web平台上线后,需要屏蔽某个服务接口,但又不想重新上线,可以采用nginx屏蔽指定平台接口的办法 Step2:具体操作 location /dist/views/landing/UNIQUE_BEACON_URL { re...

Linux_Anna
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部