Day 24 贪心算法part02| LeetCode 122.买卖股票的最佳时机II，55.跳跃游戏，45.跳跃游戏II，1005.K次取反后最大化的数组和

122.买卖股票的最佳时机II

• 局部最优：每天的正利润
• 全局最优：每天的正利润之和

121. 买卖股票的最佳时机

  class Solution {
        public int maxProfit(int[] prices) {
            int res=0;
            for(int i=1;i< prices.length;i++)
            {
              if(prices[i]-prices[i-1]>0)
              {
                  res+=prices[i]-prices[i-1];
              }

            }
           return res;
        }
    }

55.跳跃游戏

55. 跳跃游戏

• 看覆盖范围

 class Solution {
        public boolean canJump(int[] nums) {

            int cover=0;//覆盖下标
            int lens=nums.length;
            if(lens==1)return true;
            for(int i=0;i<=cover;i++)
            {
                //确保cover每次都是最大覆盖范围
                cover=Math.max(cover,i+nums[i]);
                if(cover>=lens-1)return true;

            }
            return false;
        }
    }

45.跳跃游戏II

45. 跳跃游戏 II

class Solution {
        public int jump(int[] nums) {
            if(nums.length==1)return 0;
            
                int cur_cover=0;
                int max_cover=0;//最大的覆盖范围
                int res=0;
                for(int i=0;i<nums.length;i++)
                {
                    max_cover=Math.max(i+nums[i],max_cover);
                    if(max_cover>=nums.length-1)
                    {
                        res++;
                        break;
                    }
                    if(i==cur_cover)
                    {
                        //当前终点不是数组终点
                       cur_cover=max_cover;
                      res++;
                        
                    }
                   
                }
                return res;
        }
    }

1005.K次取反后最大化的数组和

1005. K 次取反后最大化的数组和

 class Solution {
      
      void selectSort(int a[], int n)
        {
            for (int i = 0; i < n - 1; i++)
            {
                int max = i;
                for (int j = i + 1; j < n; j++)
                {
                    if (Math.abs(a[j]) > Math.abs(a[max]))//按绝对值大小比较
                    {
                        max = j;
                    }
                }
                if (max != i)
                {
                    int temp=a[i];
                    a[i]=a[max];
                    a[max]=temp;
                    //swap(a[i], a[max]);
                }
            }
        }
        public int largestSumAfterKNegations(int[] nums, int k) {

          //1.按绝对值降序排序
            selectSort(nums,nums.length);
            //2.从前往后将负数变为正数
            for(int i=0;i<nums.length;i++)
            {
                 if(nums[i]<0&&k>0)
                {
                    nums[i]= Math.abs(nums[i]);
                    k--;
                }
            }
            //3.处理剩余的k>0，反复转变绝对值最小的数，知道k==0
           if(k>0&&k%2!=0)//奇数
           {
              nums[nums.length-1]=-1*nums[nums.length-1];
           }
        
           int res=0;
           for(int i=0;i<nums.length;i++)
           {
               res+=nums[i];
           }
           return res ;
        }
    }