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]
依次取数组中的最大值进行累加
取完指定次数后,累加值即为最优解
在这个过程中,每次取最大面额的钞票为局部最优,通过每次获得局部最优得到的结果即为全局最优。
注意:贪心算法并没有固定套路,也没有固