分发饼干
力扣题目链接
思路：大饼干优先满足胃口大的孩子。
var findContentChildren = function(g, s) {
g.sort((a,b)=>a-b)
s.sort((a,b)=>a-b)
let res=0
let index=s.length-1
for(let i=g.length-1;i>=0;i--){
if(index>=0 && g[i]<=s[index]){
res++
index--
}
}
return res
};
摆动序列
leecode题目
思路：
局部最优：单调坡的元素都删除掉
全局最优：得到最长摆动序列
image.png
分析：
三种情况：
- 上下坡有平坡
- 只有首尾元素
- 单调坡有平坡
var wiggleMaxLength = function(nums) {
let res=1 //初始为1:默认最后一个元素有摆动
let preDiff=0
let curDiff=0
for(let i=0;i<nums.length-1;i++){
curDiff= nums[i+1]-nums[i]
if(preDiff <=0 && curDiff>0){
res++
preDiff= curDiff
}else if(preDiff >=0 && curDiff <0){
res++
preDiff= curDiff
}
}
return res
};
最大子数组
力扣题目链接
思路：
局部最优：当连续和为负数时，选择下一个数作为新的起点，重新开始计算连续和
全局最优：找到最大连续子数组
var maxSubArray = function(nums) {
let count=0
let res=nums[0]
for(let i=0;i<nums.length;i++){
count +=nums[i]
res=Math.max(res,count)
if(count<0){
count = 0
}
}
return res
};
