1. 152乘积最大连续子数组
题目描述：
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
152乘积最大连续子数组
思路：
这道题跟day5的连续子数组最大和有点类似，感觉可以说是它的变形。
如果我们仅仅使用连续子数组最大和的方法，假设数组全是正数，也是可以得到正确结果的，但是假设出现，a,b,c,d是连续的子数组值，axb<0,c>0,d<0，c>max(|a|,|b|)此时c的dp=c,而d的dp也=c,但是我们知道这时候的连续子数组的最大乘积应该是abcd的乘积。
上述例子我们可以知道，因为涉及到正负数的问题，所以可能导致我们的结果出错，所以我们考虑把正负数分开计算。对于一个正数来说，最大连续子数组的乘积应该等于 以它前一个数组值结尾的连续子数组的最大乘积 与它的乘积和它本身的最大值，对于负数来说，最大连续子数组的乘积应该等于 以它前一个数组值结尾的连续子数组的最小乘积与它的乘积 和它本身的最大值。文字有点抽象，先用代码表示再解释。
int maxValue = nums[0], minValue = nums[0];
int[] max = new int[nums.length];//以i结尾的最大连续子数组乘积
int[] min = new int[nums.length];//以i结尾的最小连续子数组乘积
max[0] = min[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
int tmp = nums[i];
if (tmp > 0) {
max[i] = Math.max(max[i - 1] * tmp, tmp);
min[i] = Math.min(min[i - 1] * tmp, tmp);
} else {
max[i] = Math.max(min[i - 1] * tmp, tmp);
min[i] = Math.min(max[i - 1] * tmp, tmp);
}
maxValue = Math.max(max[i], maxValue);
}
对于一个负数来说，要获取以他结尾的连续子数组最大乘积，就需要获取以她前一个结尾的连续子数组最小乘积，假设之前的最小乘积是负数，一个负数✖️一个最小的负数就可以得到一个最大的正数；假设之前的最小乘积是正数，一个负数乘以一个最小的正数所得到的负数也是最大的负数，是以当前数值结尾的最大的乘积。
所以说我们需要两个数组dp,连续子数组最大乘积和连续子数组最小乘积，并且维护他们的值。维护这两个数组的值需要分成两种情况。第一种是当前结尾的数值大于0，此时两个数组的维护方法跟连续子数组最大和一样。第二种是以当前结尾的数值小于0，我们所取得需要乘起来的数组就刚好相反。
2. 1567乘积为正的最长子数组长度
题目描述：
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
思路：
这题跟152类似，因为乘积涉及到正负数，需要定义两个dp,分别是以i结尾的乘积为正数的最长子数组长度和以i结尾的乘积为负数的最长子数组长度，代码如下：
int[] productUp = new int[nums.length];//以i结尾的乘积为正数的最长子数组长度
int[] productDown = new int[nums.length];//以i结尾的乘积为负数的最长子数组长度
if (nums[0] > 0)
productUp[0] = 1;
else if (nums[0] < 0)
productDown[0] = 1;
int maxCount = productUp[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > 0) {
productUp[i] = productUp[i - 1] + 1;
productDown[i] = productDown[i - 1] > 0 ? productDown[i - 1] + 1 : 0;
} else if (nums[i] < 0) {
productDown[i] = productUp[i - 1] + 1;
productUp[i] = productDown[i - 1] > 0 ? productDown[i - 1] + 1 : 0;
} else {
productDown[i] = 0;
productUp[i] = 0;
}
maxCount = Math.max(maxCount, productUp[i]);
}
首先初始化，如果第一个数组值大于0，那么给正数dp赋初值1，小于0则给负数dp赋初始值1.
然后如果当前值为正数，则正数dp值为它前一个结尾的正数dp的长度加1，负数dp的值为 如果它前面有连续的乘积为负数子数组，则在此基础上加一，否则置0。当值为负数时类似。当当前值是0时，需要特殊判断，此时两个dp的值都是0。
3. 1014最佳观光组合
题目描述：
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
思路：
这题印象太深刻了，感觉是一道数学题。
直接写代码吧，有兴趣看下官方给的题解。
int[] points = new int[values.length];//以景点i结尾的官网景点的评分
points[1] = values[1]+values[0]-1;
int pointMax = points[1];
int maxI = values[0]>values[1]+1?values[0]:values[1]+1;
//values[j]+values[i]+i-j (i<j)
for (int i = 2; i < values.length; i++) {
points[i] = maxI+values[i]-i;
maxI = Math.max(values[i]+i,maxI);
pointMax = Math.max(pointMax,points[i]);
}
return pointMax;
4. 121买卖股票的最佳时机
题目描述:
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
思路：
在一次遍历的时候，我们记录下股票最低价，然后遍历到每个值的时候都看当前价格与最低价的差值是不是最大的。
int maxProfit = 0;
int lowValue = prices[0];
for (int i = 1; i < prices.length; i++) {
int currentMax = 0;
if (prices[i]> lowValue) {
currentMax = prices[i]-lowValue;
}
lowValue = Math.min(lowValue,prices[i]);
maxProfit = Math.max(currentMax,maxProfit);
}
5. 122买卖股票的最佳时机2
题目描述：
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
思路：
第一想到的就是贪心，如果今天有利润，就出售
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i]>prices[i-1]){
//如果今天有利润，就出售
maxProfit += prices[i]-prices[i-1];
}
}
动态规划看题解吧 有点懒得写了。。。