K次取反后最大化的數(shù)組

力扣題目鏈接
局部最優(yōu)：讓絕對值大的負數(shù)變?yōu)檎龜?shù)，當(dāng)前數(shù)值達到最大发魄，整體最優(yōu)：整個數(shù)組和達到最大巩梢。
如果將負數(shù)都轉(zhuǎn)變?yōu)檎龜?shù)了玄货，K依然大于0港华，此時的問題是一個有序正整數(shù)序列，如何轉(zhuǎn)變K次正負，讓數(shù)組和 達到最大。

那么又是一個貪心：局部最優(yōu)：只找數(shù)值最小的正整數(shù)進行反轉(zhuǎn)错邦，當(dāng)前數(shù)值和可以達到最大（例如正整數(shù)數(shù)組{5, 3, 1}，反轉(zhuǎn)1 得到-1 比 反轉(zhuǎn)5得到的-5 大多了）型宙，全局最優(yōu)：整個 數(shù)組和 達到最大撬呢。

//自己寫的，時間復(fù)雜度和空間復(fù)雜度高妆兑。

var largestSumAfterKNegations = function(nums, k) {
   while (k--) {
    nums.sort((a, b) => {
      return a - b;
    });
    nums[0] = -nums[0];
  }

  return nums.reduce((pre, cur) => {
    return pre + cur;
  }, 0);
  
};

改進：
通過采用絕對值排序魂拦，先把負數(shù)轉(zhuǎn)換，未用完的k搁嗓，再從正數(shù)中芯勘，找最后一個值，不必每次轉(zhuǎn)換腺逛，通過奇偶數(shù)判斷最后的正負荷愕。

var largestSumAfterKNegations = function(nums, k) {
   nums.sort((a,b)=>{
       return Math.abs(b)-Math.abs(a)
   })
   for(let i in nums){
       if(nums[i]<0 && k>0){
           nums[i]=-nums[i]
           k--
       }
   }
   if( k % 2 === 1){
       nums[nums.length-1]=-nums[nums.length-1]
   }
   return nums.reduce((pre,cur)=>{
       return pre+cur
   },0)
};

加油站

思路：
局部最優(yōu)：當(dāng)前累加和curSum一旦小于0，起始位置至少要是i+1，因為從i之前開始一定不行安疗。
全局最優(yōu)：找到可以跑一圈的起始位置抛杨。

image.png

力扣題目鏈接

var canCompleteCircuit = function(gas, cost) {
    let curSum=0
    let totalSum=0
    let res =0

    for(let i=0;i<gas.length;i++){
        curSum += gas[i]-cost[i]
        totalSum +=gas[i]-cost[i]
        if(curSum<0){
            res = i+1
            curSum=0
        }
    }
    if(totalSum<0) return -1
    return res
};

分發(fā)糖果

力扣題目鏈接

思路：
確定一邊之后，再確定另一邊荐类，

1. 右邊比左邊大：
   局部最優(yōu)：只要右邊評分比左邊大怖现，右邊的孩子就多一個糖果，全局最優(yōu)：相鄰的孩子中玉罐，評分高的右孩子獲得比左邊孩子更多的糖果
2. 左邊比右邊大：
   局部最優(yōu)：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果數(shù)量屈嗤，保證第i個小孩的糖果數(shù)量既大于左邊的也大于右邊的。全局最優(yōu)：相鄰的孩子中厌小，評分高的孩子獲得更多的糖果恢共。

var candy = function(ratings) {
    let candy =[]
    candy[0]=1
    for(let i=1;i<ratings.length;i++){
        if(ratings[i]>ratings[i-1]){
            candy[i]=candy[i-1]+1
        }else{
            candy[i]=1
        }
    }

    for(let i=ratings.length-2;i>=0;i--){
        if(ratings[i]>ratings[i+1]){
            candy[i]=Math.max(candy[i+1]+1,candy[i])
        }
    }
    return candy.reduce((pre,cur)=>{
        return pre+cur
    },0)
};