旅游网站开发开题报告,保险网站建设的总体目标,广州市重点公共建设项目官网,成交型网站建设方案1. 最大子序和
53. 最大子数组和https://leetcode.cn/problems/maximum-subarray/
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组#xff1a;是数组中的一个连续…1. 最大子序和
53. 最大子数组和https://leetcode.cn/problems/maximum-subarray/
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组是数组中的一个连续部分。
示例 1
输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 。
示例 2
输入nums [1]
输出1
示例 3
输入nums [5,4,-1,7,8]
输出23
解题思路
最短的序列就是单个用贪心的思路来做首先需要找到局部最优。当累加到当前是负数的时候就放弃累加改当前为起始。考虑下这样能不能覆盖到最大子序列的情况。最大子序列的中间不会出现这个情况因为出现了的话那么就说明有一部分可以舍弃得到更大的子序列。左右也不会因为左右一定是负数且累加到的时候一定小于0。
代码
class Solution {public int maxSubArray(int[] nums) {if (nums.length 1)return nums[0];int max nums[0];int cur nums[0];for (int i 1; i nums.length; i) {cur Math.max(nums[i], cur nums[i]);//对当前节点来说最优解为加上和本身为开始的两种情况max Math.max(cur, max);}return max;}
}
2. 买卖股票的最佳时机 II
122. 买卖股票的最佳时机 IIhttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1
输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4 。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3 。总利润为 4 3 7 。
示例 2
输入prices [1,2,3,4,5]
输出4
解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出,这笔交易所能获得利润 5 - 1 4 。总利润为 4 。
示例 3
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为 0 。
解题思路
有个最基本的思想就是抄底和高部套现。所以一个基本的思路模型就是找到一段递减序列的最低点然后找到一段递增的最高。这就是局部最优解了开始考虑这样的局部最优会不会影响整体最优在局部最优内部是不会影响的也就是需要考虑多个局部最优是否能够得到一个整体最优也就是验证贪心算法的正确性。
一共局部最优的时候满足整体最优假设第k个局部最优的时候满足整体最优
第k个局部最优是不操作已经遍历完了第k个局部最优有赚
那么第k1个可以进行讨论
k个不操作的情况下k1也不操作整体最优k个局部有赚的情况下k1如果局部也有赚进行分类讨论 k1 的卖出比k的卖出低或者相等的时候整体是最优k1的卖出比k的高的时候right2-left1right2-right1right1-left1right2-left1righ1-left1(因为left1是不会比righ1大的)所以一定是整体最优。
综上所述可以贪心
注每一个局部最优也是多步骤得到的也需要讨论局部最优如何实现也就是要找到一个最低买入最高卖出由于可以当如卖和买同时操作在最低点买入所以在遍历过程中只需要发现没有大于上一个买入点那就重置买入点这样能找到最佳买入点然后是卖出求的是利润在找最高点的过程中可以把整个大利润分为每天的小利润这依旧是满足贪心的正确性的一共连续非递减的部分整个大利润正好等于每天的小利润。当开始降的时候又开始了另一个局部最优的买入点的寻找。
代码 class Solution {public int maxProfit(int[] prices) {int profit 0;int buy prices[0];for (int i 1; i prices.length; i) {if (prices[i] buy) {buy prices[i];} else {profit prices[i] - buy;buy prices[i];}}return profit;}
}
