LeetCode: Maximum Product Subarray && Maximum Subarray &子序列相关

时间:2022-09-18 09:46:49

Maximum Product Subarray

Title:

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.

对于Product Subarray,要考虑到一种特殊情况,即负数和负数相乘:如果前面得到一个较小的负数,和后面一个较大的负数相乘,得到的反而是一个较大的数,如{2,-3,-7},所以,我们在处理乘法的时候,除了需要维护一个局部最大值,同时还要维护一个局部最小值,由此,可以写出如下的转移方程式:

max_copy[i] = max_local[i]
max_local[i + 1] = Max(Max(max_local[i] * A[i], A[i]),  min_local * A[i])

min_local[i + 1] = Min(Min(max_copy[i] * A[i], A[i]),  min_local * A[i])

class Solution {
public:
int maxProduct(vector<int>& nums) {
int pmin = nums[];
int pmax = nums[];
int result = nums[];
for (int i = ; i < nums.size(); i++){
int t1= pmax * nums[i];
int t2= pmin * nums[i];
pmax = max(nums[i],max(t1,t2));
pmin = min(nums[i],min(t1,t2));
result = max(result,pmax);
}
return result;
}
};

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

http://blog.csdn.net/joylnwang/article/details/6859677

http://blog.csdn.net/linhuanmars/article/details/21314059

class Solution{
public:
int maxSubArray(int A[], int n) {
int maxSum = A[];
int sum = A[];
for (int i = ; i < n; i++){
if (sum < )
sum = ;
sum += A[i];
maxSum = max(sum,maxSum);
}
return maxSum;
}
};

扩展:子序列之和最接近于0

先对数组进行累加,这样得到同样长度的数组,然后,对数组排序,对排序后的数组相邻的元素相减计算绝对值,并比较大小。

class Solution{
public:
vector<int> simple(vector<int> nums,int target){
int min_gap = INT_MAX;
int index_min ;
int index_max;
for (int i = ; i < nums.size(); i++){
int sum = ;
for (int j = i; j < nums.size(); j++){
sum += nums[j];
if (min_gap > abs(sum-target)){
min_gap = abs(sum-target);
index_min = i;
index_max = j;
}
}
}
vector<int> result(nums.begin()+index_min,nums.begin()+index_max+);
return result;
}
vector<int> choose(vector<int> nums, int target){
vector<pair<int,int> > addSums(nums.size());
addSums[] = make_pair(nums[],);
for (int i =; i < nums.size(); i++){
addSums[i] = make_pair(addSums[i-].first + nums[i],i);
}
sort(addSums.begin(),addSums.end());
int min_gap = INT_MAX;
int index = -;
for (int i = ; i < addSums.size(); i++){
int t = abs(addSums[i].first - addSums[i-].first);
if (min_gap > t){
min_gap = t;
index = i;
}
}
int index_min = min(addSums[index].second,addSums[index-].second);
int index_max = max(addSums[index].second,addSums[index-].second);
vector<int> result(nums.begin()+index_min+,nums.begin()+index_max+);
return result;
}
};

这种做法我没有想到如何扩展到任意的t上面

LeetCode: Maximum Product Subarray && Maximum Subarray &子序列相关的更多相关文章

  1. 求连续最大子序列积 - leetcode&period; 152 Maximum Product Subarray

    题目链接:Maximum Product Subarray solutions同步在github 题目很简单,给一个数组,求一个连续的子数组,使得数组元素之积最大.这是求连续最大子序列和的加强版,我们 ...

  2. LeetCode Maximum Product Subarray(枚举)

    LeetCode Maximum Product Subarray Description Given a sequence of integers S = {S1, S2, . . . , Sn}, ...

  3. &lbrack;Swift&rsqb;LeetCode152&period; 乘积最大子序列 &vert; Maximum Product Subarray

    Given an integer array nums, find the contiguous subarray within an array (containing at least one n ...

  4. &lbrack;LeetCode&rsqb; Maximum Product Subarray 求最大子数组乘积

    Find the contiguous subarray within an array (containing at least one number) which has the largest ...

  5. &lbrack;LeetCode&rsqb; 152&period; Maximum Product Subarray 求最大子数组乘积

    Given an integer array nums, find the contiguous subarray within an array (containing at least one n ...

  6. 【LeetCode】Maximum Product Subarray 求连续子数组使其乘积最大

    Add Date 2014-09-23 Maximum Product Subarray Find the contiguous subarray within an array (containin ...

  7. [LeetCode]152&period; Maximum Product Subarray

    This a task that asks u to compute the maximum product from a continue subarray. However, you need t ...

  8. leetcode 53&period; Maximum Subarray 、152&period; Maximum Product Subarray

    53. Maximum Subarray 之前的值小于0就不加了.dp[i]表示以i结尾当前的最大和,所以需要用一个变量保存最大值. 动态规划的方法: class Solution { public: ...

  9. 【Leetcode】Maximum Product Subarray

    Find the contiguous subarray within an array (containing at least one number) which has the largest ...

随机推荐

  1. eclipse导入JDK源码

    前言:这件事情的重要性不言而喻,对于学习和观摩优秀的代码非常的有用,我喜欢想看什么代码都能 Ctrl+鼠标一点 就能够看到,不过这个不常操作,在这里小记一笔,以备后用.(完全是傻瓜式的记录,就是怕自己 ...

  2. Java &lbrack;leetcode 8&rsqb; String to Integer &lpar;atoi&rpar;

    问题描述: Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input ...

  3. The First Pig Task

                         The First Pig Program 环境: Hadoop-1.1.2 pig-0.11.1 linux系统为CentOS6.4 jdk1.6 在伪分布 ...

  4. Perfect Squares——Leetcode

    Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 1 ...

  5. SVN导出增量包的方法

    此方法是在svn1.7版本基础上进行的操作,其他版本没有验证 第一步.点击右键,选择“TortoiseSVN–> Show log”. 进入日志页面,如下图所示: 第二步.选择版本区间,右键选择 ...

  6. codeforces 401D&period; Roman and Numbers 数位dp

    题目链接 给出一个<1e18的数, 求将他的各个位的数字交换后, 能整除m的数的个数. 用状态压缩记录哪个位置的数字已经被使用了, 具体看代码. #include<bits/stdc++. ...

  7. 如何在office2007中插入MathType教学

    很多人在安装MathType数学公式编辑器时可能会遇到这个问题,MathType安装好了,可是在office2007的菜单栏中没有MathType这个选项卡,也就是说MathType没有成功加载在of ...

  8. 12、类成员访问修饰符public&sol;private&sol;producted&sol;readonly

    1.private 类的私有成员 private 类的私有成员,只能在内部访问,在外部访问不到,无法被继承,我们可以将不需要被外部修改的定义为私有的 私有成员,只能在内部访问,在外部访问不到 priv ...

  9. debian proftpd安装

  10. xmlhttprequest readyState 属性的五种状态

    关于readystate五个状态总结如下: readyState 状态    状态说明(0)未初始化此阶段确认XMLHttpRequest对象是否创建,并为调用open()方法进行未初始化作好准备.值 ...