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

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

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

//自己寫(xiě)的，時(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);
  
};

改進(jìn)：
通過(guò)采用絕對(duì)值排序，先把負(fù)數(shù)轉(zhuǎn)換，未用完的k，再?gòu)恼龜?shù)中，找最后一個(gè)值，不必每次轉(zhuǎn)換，通過(guò)奇偶數(shù)判斷最后的正負(fù)。

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，因?yàn)閺膇之前開(kā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)：只要右邊評(píng)分比左邊大，右邊的孩子就多一個(gè)糖果，全局最優(yōu)：相鄰的孩子中，評(píng)分高的右孩子獲得比左邊孩子更多的糖果
2. 左邊比右邊大：
   局部最優(yōu)：取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果數(shù)量，保證第i個(gè)小孩的糖果數(shù)量既大于左邊的也大于右邊的。全局最優(yōu)：相鄰的孩子中，評(píng)分高的孩子獲得更多的糖果。

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)
};