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

Leetcode 2786. 访问数组中的位置使分数最大(DP 优化)

Leetcode 2786. 访问数组中的位置使分数最大

DP
以每个位置为结尾的序列的分数取决于前方的分数,根据奇偶性计算,取最大值
超时

class Solution {public long maxScore(int[] nums, int x) {int n = nums.length;long dp[] = new long[n];Arrays.fill(dp, Integer.MIN_VALUE);dp[0] = nums[0];long res = nums[0];for(int i = 1; i < n; i ++){for(int j = 0; j < i; j ++){if(nums[j] % 2 == nums[i] % 2){dp[i] = Math.max(dp[i], dp[j] + nums[i]);}else{dp[i] = Math.max(dp[i], dp[j] + nums[i] - (long)x);}}res = Math.max(res, dp[i]);}return res;}
}

优化

对于 nums[ i ] 来说,该位置的分数取决于前方的序列分数,分为上一个选择是奇数和偶数两种情况,只需max0、max1来分别记录前方的奇偶两种情况最值即可计算出当前位置的分数最值

避免思维误区,计算cur时考虑的不是选或不选的两种情况,而是必定选择 nums[ i ] 作为序列最后一个元素时,取前方奇偶两种可能所获得的分数哪一种更大

由于存在x值较大的情况,计算中可能出现负数,将max0、max1初始化为INT_MIN

获取最值后根据 nums[ i ] 的奇偶性选择更新max0或max1
计算max0/1的两种可能时,即使有可能异性-x后的分数更大,但由于存在同性计算 — 两个正数相加,因此max0/1的值必定会增大,直接将cur赋值给max0/1

class Solution {public long maxScore(int[] nums, int x) {int n = nums.length;long max0 = Integer.MIN_VALUE; // 前方偶数结尾的最大分数long max1 = Integer.MIN_VALUE; // 前方奇数结尾的最大分数if(nums[0] % 2 == 0)max0 = nums[0];elsemax1 = nums[0];long res = nums[0];for(int i = 1; i < n; i ++){long cur;if(nums[i] % 2 == 0){cur = Math.max(max0 + nums[i], max1 + nums[i] - x);max0 = cur;// max0 = Math.max(max0, cur);// 同性情况max0+nums[i],正数求和计算导致cur必然大于max0,省去Max计算}else{cur = Math.max(max0 + nums[i] - x, max1 + nums[i]);max1 = cur;}res = Math.max(res, cur);}return res;}
}

相关文章:

Leetcode 2786. 访问数组中的位置使分数最大(DP 优化)

Leetcode 2786. 访问数组中的位置使分数最大 DP 以每个位置为结尾的序列的分数取决于前方的分数&#xff0c;根据奇偶性计算&#xff0c;取最大值 超时 class Solution {public long maxScore(int[] nums, int x) {int n nums.length;long dp[] new long[n];Arrays.fill(dp…...

【docker实战】使用Dockerfile的COPY拷贝资源遇到的问题

事情是这样的。 在我负责的golang项目中&#xff0c;使用硬代码验证某块逻辑。比如&#xff1a; 于是&#xff0c;为了解决硬代码的问题&#xff0c;我制作了表格工具&#xff1a;【开源项目】Excel数据表自动生成工具v1.0版 – 经云的清净小站 (skycreator.top)。 使用表格工…...

如何用多线程执行 unittest 测试用例实现方案

前言 使用python做过自动化测试的小伙伴&#xff0c;想必都知道unittest和pytest这两个单元测试框架&#xff0c;其中unittest是python的官方库&#xff0c;功能相对于pytest来要逊色不少&#xff0c;但是uniitest使用上手简单&#xff0c;也受到的很多的小伙伴喜爱。一直以来都…...

Ascend310 EP模式下容器内进行推理测试

EP模式下容器内进行推理测试 本文的软硬件环境如下&#xff1a; 机器&#xff1a;x86台式机一台 OS&#xff1a; 5.4.0-26-generic Ubuntu20.04 LTS 推理卡&#xff1a;DLAP200-HP-2&#xff08;凌华基于atlas200模块打造的两模块推理卡&#xff09; 1. 推理卡固件和驱动安…...

(el-Transfer)操作(不使用 ts):Element-plus 中 Select 组件动态设置 options 值需求的解决过程

Ⅰ、Element-plus 提供的Select选择器组件与想要目标情况的对比&#xff1a; 1、Element-plus 提供Select组件情况&#xff1a; 其一、Element-ui 自提供的Select代码情况为(示例的代码)&#xff1a; // Element-plus 提供的组件代码: <template><div class"f…...

Java基础之Math与Array类与System

文章目录 一、Math.random&#xff08;&#xff09;二、Arrays.binarySearch()三、asList&#xff08;&#xff09;四、System tip&#xff1a;以下是正文部分 一、Math.random&#xff08;&#xff09; a < num < b int num (int)(Math.random() * (b - a 1)) a二、…...

警告:Hydration attribute mismatch on Note: this mismatch is check-only.(水合不匹配)

vue3Nuxt3运行代码是提示如下警告 [Vue warn]: Hydration attribute mismatch on <ul id​"sub_menu_5_$$_sub1-popup" class​"ant-menu ant-menu-sub ant-menu-inline" data-menu-list​"true" style​"display:​none;​">​…...

【机器学习】CART决策树算法的核心思想及其大数据时代银行贷款参考案例——机器认知外界的重要算法

目录 引言 概述 CART决策树的特点 核心思想 减少不确定性的指标 基尼系数&#xff08;Gini Index&#xff09; 分类错误率 熵 银行实例 背景 数据准备 模型构建 模型评估与优化 应用与结果 代码示例 ✈✈✈✈引言✈✈✈✈ CART算法既可以用于分类问题&#xff0…...

编程软件是由什么编程的

编程软件是由什么编程的 在数字化的世界里&#xff0c;编程软件作为构建数字生态的基石&#xff0c;其背后所蕴含的奥秘往往令人感到困惑。那么&#xff0c;这些编程软件究竟是由什么编程的呢&#xff1f;这背后隐藏着怎样的逻辑与技术&#xff1f;接下来&#xff0c;我们将从…...

如何查看自己本地ip

1.winR 2.cmd 3.ipconfig...

高考分数限制下,选好专业还是选好学校?

高考分数限制下&#xff0c;选好专业还是选好学校&#xff1f; 高考作为每年一度的盛大考试&#xff0c;不仅关乎学生们的未来&#xff0c;更承载了家庭的期望。2004年高考刚刚结束&#xff0c;许多考生和家长已经开始为填报志愿而焦虑。选好学校和专业&#xff0c;直接关系到…...

Django学习(2)项目实战

1、环境及简介 前端开发&#xff1a;HTML、CSS、JavaScript 后端开发&#xff1a;Java、PHP、Python、GO 数据库&#xff1a;MySQL、MSSQL、Oracle、Redis 安装Django pip install Django 或 下载.whl后 pip install D&#xff1a;\xxx.whl 创建Django项目 File--New Projec…...

pdf格式转成jpg图片,pdf格式如何转jpg

pdf转图片的方法&#xff0c;对于许多人来说可能是一个稍显陌生的操作。然而&#xff0c;在日常生活和工作中&#xff0c;我们有时确实需要将pdf文件转换为图片格式&#xff0c;以便于在特定的场合或平台上进行分享、展示或编辑。以下&#xff0c;我们将详细介绍一个pdf转成图片…...

Java的三个接口Comparable,Comparator,Cloneable(浅拷贝与深拷贝)

Comparable 当我们要进行对象的比较的时候&#xff0c;我们是不能直接用>、< 这些符号直接进行比较的。 由于这是引用类型变量也是自定义类型变量&#xff0c;直接进行比较的时候&#xff0c;我们是通过对象的地址进行比较的&#xff0c;我们可以使用、! 进行两个对象的…...

pytorch学习笔记7

getitem在进行索引取值的时候自动调用,也是一个魔法方法,就像列表索引取值那样,一个意思 import torchvision from torch.utils.data import DataLoaderdata_transformtorchvision.transforms.Compose([torchvision.transforms.ToTensor()] ) test_datatorchvision.datasets.C…...

LeetCode热题3.无重复的最长字串

前言: 经过前序的一系列数据结构和算法学习后&#xff0c;开始用leetCode热题练练手。 . - 力扣&#xff08;LeetCode&#xff09; 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的最长子串的长度。 示例 1: 输入: s "abcabcbb" 输出: 3 解释: 因为…...

Python武器库开发-武器库篇之SQL注入扫描器(五十九)

Python武器库开发-武器库篇之SQL注入扫描器(五十九) SQL注入漏洞简介以及危害 SQL注入漏洞是一种常见的Web应用程序漏洞&#xff0c;攻击者可以利用该漏洞在应用程序的数据库中执行恶意的SQL查询或指令。这可能导致数据泄露、数据损坏、应用程序崩溃或未经授权的访问。 SQL注…...

图说设计模式:单例模式

更多C学习笔记&#xff0c;关注 wx公众号&#xff1a;cpp读书笔记 5. 单例模式 单例模式 模式动机模式定义模式结构时序图代码分析模式分析实例优点缺点适用环境模式应用模式扩展总结 5.1. 模式动机 对于系统中的某些类来说&#xff0c;只有一个实例很重要&#xff0c;例如…...

探索设计模式——单例模式详解

前言&#xff1a;设计模式的作用主要是为了——利用设计方式的重用来自动地提高代码的重新利用、提高代码的灵活性、节省时间&#xff0c; 提高开发效率、低耦合&#xff0c;封装特性显著&#xff0c; 接口预留有利于扩展。 设计模式的种类有很多种&#xff0c;本篇内容主要讲解…...

建筑垃圾/城市固废倾倒转移乱象:EasyCVR+AI智能视频监控方案助力城市环保监管

近日有新闻记者报道&#xff0c;中央生态环境保护督察组在上海、浙江、江西、湖北、湖南、重庆、云南7省市督察发现&#xff0c;一些地方建筑垃圾处置工作存在明显短板&#xff0c;乱堆乱倒问题时有发生&#xff0c;比如&#xff0c;江西湘东区在杨家田地块违规设置弃土场&…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...