2024-11-29
642 字
2 分钟
最大子序和
题目
给定一个整数数组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
《代码随想录》算法公开课
力扣题目链接
思路
暴力解法
暴力解法的思路，第一层for就是设置起始位置，第二层 for循环遍历数组寻找最大值
1234567891011121314151617181920class
2024-11-28
897 字
3 分钟
摆动序列
题目
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
例如，[1,7,4,9,2,5]是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和[1,7,4,5,5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
示例1
输入: [1,7,4,9,2,5]
输
2024-11-28
967 字
3 分钟
贪心算法-分发饼干
什么是贪心算法
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
例如有一堆不同数额的钞票，每次只能拿一张，怎么拿能取得最大数额的钞票。
方法：将钞票从大到小进行排序，每次都拿走当前堆里最大面额的钞票，即可在指定拿取次数中获得最大数额的钞票。
例如：[100, 100, 50, 20, 50, 1, 10]
排序后为：[100, 100, 50, 50, 20, 10, 1]
依次取数组中的最大值进行累加
取完指定次数后，累加值即为最优解
在这个过程中，每次取最大面额的钞票为局部最优，通过每次获得局部最优得到的结果即为全局最优。
注意：贪心算法并没有固定套路，也没有固
