目录
最⻓连续递增序列（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个未经排序的整数数组，找到最⻓且连续递增的⼦序列，并返回该序列的⻓度。
连续递增的⼦序列可以由两个下标 l 和 r （ l < r ）确定，如果对于每个 l <= i < r ，都有 nums[i] < nums[i + 1] ，那么⼦序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增⼦序列。
⽰例1：
输⼊：nums=[1,3,5,4,7]
输出：3
解释：最⻓连续递增序列是[1,3,5],⻓度为3。
尽管[1,3,5,7]也是升序的⼦序列,但它不是连续的，因为5和7在原数组⾥被4隔开。
⽰例2：
输⼊：nums=[2,2,2,2,2]
输出：1
解释：最⻓连续递增序列是[2],⻓度为1。
提⽰：
◦ 1 <= nums.length <= 10(4)
◦ -10(9) <= nums[i] <= 10(9)
讲解算法原理
解法（贪⼼）：
贪⼼策略：
找到以某个位置为起点的最⻓连续递增序列之后（设这个序列的末尾为 j 位置），接下来直接以 j + 1 的位置为起点寻找下⼀个最⻓连续递增序列。
编写代码
c++算法代码：
class Solution
{
public:
int findLengthOfLCIS(vector<int>& nums)
{
int ret = 0, n = nums.size();
for(int i = 0; i < n; )
{
int j = i + 1;
// 找到递增区间的末端
while(j < n && nums[j] > nums[j - 1]) j++;
ret = max(ret, j - i);
i = j; // 直接在循环中更新下⼀个位置的起点 }
return ret;
}
};java算法代码：
class Solution
{
public int findLengthOfLCIS(int[] nums)
{
int ret = 0, n = nums.length;
for(int i = 0; i < n; )
{
int j = i + 1;
// 找到递增区间的末端
while(j < n && nums[j] > nums[j - 1]) j++;
ret = Math.max(ret, j - i);
i = j; // 循环内部直接更新下⼀个位置的起点 - 贪⼼ }
return ret;
}
}买卖股票的最佳时机（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个数组 prices ，它的第 i 个元素 prices[i] 表⽰⼀⽀给定股票第 i 天的价格。你只能选择某⼀天买⼊这只股票，并选择在未来的某⼀个不同的⽇⼦卖出该股票。设计⼀个算法来
计算你所能获取的最⼤利润。
返回你可以从这笔交易中获取的最⼤利润。如果你不能获取任何利润，返回 0 。
⽰例1：
输⼊：[7,1,5,3,6,4]
输出：5
解释：在第2天（股票价格=1）的时候买⼊，在第5天（股票价格=6）的时候卖出，最⼤利润=6-1=5。
注意利润不能是7-1=6,因为卖出价格需要⼤于买⼊价格；同时，你不能在买⼊前卖出股票。⽰例2：
输⼊：prices=[7,6,4,3,1]
输出：0
解释：在这种情况下,没有交易完成,所以最⼤利润为0。
提⽰：
◦ 1 <= prices.length <= 10(5)
◦ 0 <= prices[i] <= 10(4)
讲解算法原理
解法（贪⼼）：
贪⼼策略：
由于只能交易⼀次，所以对于某⼀个位置 i ，要想获得最⼤利润，仅需知道前⾯所有元素的最⼩值。然后在最⼩值的位置「买⼊」股票，在当前位置「卖出」股票即可。
编写代码
c++算法代码：
class Solution
{
public:
int maxProfit(vector<int>& prices)
{
int ret = 0; // 记录最终结果
for(int i = 0, prevMin = INT_MAX; i < prices.size(); i++)
{
ret = max(ret, prices[i] - prevMin); // 先更新结果
prevMin = min(prevMin, prices[i]); // 再更新最⼩值
}
return ret;
}
};java算法代码：
class Solution
{
public int maxProfit(int[] prices)
{
int ret = 0; // 记录最终结果
for(int i = 0, prevMin = Integer.MAX_VALUE; i < prices.length; i++)
{
ret = Math.max(ret, prices[i] - prevMin); // 先更新结果
prevMin = Math.min(prevMin, prices[i]); // 再更新最⼩值
}
return ret;
}
}