代码随想录刷题笔记-Day32

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个局部最优的时候满足整体最优：

1. 第k个局部最优是不操作（已经遍历完了）；
2. 第k个局部最优有赚；

那么第k+1个可以进行讨论：

1. k个不操作的情况下，k+1也不操作，整体最优
2. k个局部有赚的情况下，k+1如果局部也有赚，进行分类讨论
   1. k+1 的卖出比k的卖出低或者相等的时候，整体是最优
   2. k+1的卖出比k的高的时候，right2-left1=right2-right1+right1-left1<=right2-left1+righ1-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;}
}