当前位置: 首页 > article >正文

贪心算法(5)(java)k次取反后最大化的数组和

        题目:给定一个整数数组 `nums` 和一个整数 `k`,你可以进行最多 `k` 次取反操作。每次操作可以选择数组中的一个元素并将其取反(即 `x` 变为 `-x`)。最终返回经过 `k` 次取反操作后,数组可能的最大总和。

解法:分情况讨论。

设:整个数组中负数的个数是m个

1.m>k: 把前k小负数转化成正数

2.m==k:把所有负数全部转化成正数

3.m<k: 1..先把所有负数变成正数

            2.k-m的奇偶性1...偶数:直接忽略

                                    2...奇数:挑选当前数组中最小的数,变成负数

import java.util.Arrays;

public class Solution {
    public int largestSumAfterKNegations(int[]nums,int k){
        int m=0,minElem=Integer.MAX_VALUE,n=nums.length;
        //统计负数个数,记录绝对值最小的元素
        for(int x:nums){
            if(x<0)m++;
            //负数计数
            minElem=Math.min(minElem,Math.abs(x));
        }
        //分类讨论
        int ret=0;
        if(m>k){   //情况一:负数个数多于k次反转
            Arrays.sort(nums);//排序数组
            for(int i=0;i<k;i++){//翻转前k个负数
                ret -= nums[i];//剩余元素直接累加
            }
            for(int i=k;i<n;i++){
                ret += nums[i];
            }

        }else{//负数个数小于等于k次翻转
            //把负数全部变为正数
            for(int x:nums)ret+=Math.abs(x);
            if((k-m)%2!=0){//剩余奇数次需调整最小值
                    ret-=minElem*2;//减去两倍·最小值
                }
            }
            return ret;
        }
    public static void main(String[] args) {
        Solution solution=new Solution();
        int [] nums={2,-3,-1,5,-4};
        int result= solution.largestSumAfterKNegations(nums,2);
        System.out.println(result);
    }
}


http://www.kler.cn/a/583711.html

相关文章:

  • 什么是AI?AI能对我们生活产生哪些影响?
  • LeetCode 112. 路径总和 II java题解
  • 如何用Docker容器化Java应用?Spring Boot实战指南
  • Spring Boot 约定大于配置:实现自定义配置
  • HCIP复习拓扑练习(修改版)
  • 【3DGS】SuperSplat本地运行+修改监听端口+导入ply模型+修剪模型+在线渲染3DGS网站推荐
  • 设计模式C++
  • Java 8新特性:Lambda表达式与Stream API实战
  • OEM SQL Details and Session Details 5s 或者parallel 才会在sql monitor显示
  • Aliyun CTF 2025 web 复现
  • uniapp,自绘仪表盘组件(基础篇)
  • BEVDepth: Acquisition of Reliable Depth for Multi-view 3D Object Detection 论文阅读
  • c# txt文档的实时显示,用来查看发送接收指令
  • 如何简单获取三个月免费试用的SSL证书
  • AI对前端开发的冲击
  • 第十课:项目部署与运维:从开发到生产
  • 仅仅使用pytorch来手撕transformer架构(1):位置编码的类的实现和向前传播
  • springcloud gateway搭建及动态获取nacos注册的服务信息信息
  • aws(学习笔记第三十二课) 深入使用cdk(API Gateway + event bridge)
  • C++算法学习2:二分算法精讲