牛客NC295 连续子链表最大和【simple 动态规划 Java/Go/PHP/C++】

题目

在这里插入图片描述
题目链接:
https://www.nowcoder.com/practice/650b68dfa69d492d92645aecd7da9b21

思路

动态规划动态规划算法通过迭代遍历输入数组,维护一个额外的数组 dp 来记录截止到每个位置的最大连续子数组和,并利用一个变量 max_num 实时更新全局最大子数组和的值。算法的核心思想在于,通过比较当前元素和前一个元素的最大子数组和是否大于零,来决定是否将当前元素加入前一个子数组或者从当前元素重新开始形成子数组。最终,返回 max_num 作为最大子数组和的解。初始化dp:dp[i]表示前i个元素最大的连续子数组和状态转移:如果dp[i-1] > 0, dp[i] = dp[i-1] + nums[i],否则dp[i] = nums[i](分类讨论)初始换状态:dp[0] = nums[0]最优解:max(dp)

Java代码

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @return int整型*/public int FindGreatestSumOfSubArray (ListNode head) {//动态规划int pre = head.val;int ans = head.val;head = head.next;while(head!=null){int p1 = head.val;int p2 = head.val+pre;int cur = Math.max(p1,p2);ans = Math.max(ans,cur);pre = cur;head=head.next;}return ans;}
}

Go代码

package main
import . "nc_tools"
/** type ListNode struct{*   Val int*   Next *ListNode* }*//*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @return int整型
*/
func FindGreatestSumOfSubArray( head *ListNode ) int {//动态规划pre:=head.Valans:=head.Valhead = head.Nextfor head!=nil {p1:=head.Valp2:=head.Val+pre cur:=p1 if cur < p2 {cur =p2 }if ans < cur{ans = cur }pre = cur head =head.Next}return ans 
}

PHP代码

<?php/*class ListNode{var $val;var $next = NULL;function __construct($x){$this->val = $x;}
}*//*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @return int整型*/
function FindGreatestSumOfSubArray( $head )
{//动态规划$pre = $head->val;$ans = $head->val;$head =$head->next;while($head!=null){$p1 = $head->val;$p2 = $head->val+$pre;$cur = $p1;if($cur < $p2){$cur = $p2;}if($ans < $cur){$ans = $cur;}$pre = $cur;$head = $head->next;}return $ans;
}

C++ 代码

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param head ListNode类 * @return int整型*/int FindGreatestSumOfSubArray(ListNode* head) {//动态规划int pre = (*head).val;int ans = (*head).val;head =(*head).next;while(head !=nullptr){int p1 = (*head).val;int p2 =(*head).val+pre;int cur = p1;if(cur < p2){cur = p2;}if(ans < cur){ans = cur;}pre = cur;head=(*head).next;}return ans;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1429991.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

(优作)风力摆控制系统

本系统由瑞萨 100LGA 单片机控制模块&#xff0c; 6050 三轴陀螺仪加速度模块&#xff0c;直流风机及其驱 动模块&#xff0c;显示模块&#xff0c;键盘模块&#xff0c;蜂鸣器模块以及风力摆机械结构组成&#xff0c; MPU6050 采集风摆姿 态&#xff0c;单片机处理姿态数…

python机器学习及深度学习在空间模拟与时间预测

原文链接https://mp.weixin.qq.com/s?__bizMzUyNzczMTI4Mg&mid2247628504&idx2&sn6fe3aeb9f63203cfe941a6bb63b49b85&chksmfa77a9e5cd0020f3aa4f01887e75b15096a182c2b5b42c1044787aa285c650f1469a0ef28aec&token2124656491&langzh_CN&scene21#we…

新能源汽车的电驱热管理

前言 新能源汽车的电驱热管理是指维持电动汽车电池、电机和电控系统在适宜的工作温度范围内&#xff0c;保障车辆高效、安全、稳定运行的技术方案。随着新能源汽车的快速发展和普及&#xff0c;电驱热管理技术也日益成为关注焦点。本文将从电池、电机和电控系统三个方面介绍新…

【计算机毕业设计】基于SSM+Vue的校园美食交流系统【源码+lw+部署文档】

目录 前 言 第1章 概述 1.1 研究背景 1.2 研究目的 1.3 研究内容 第二章 开发技术介绍 2.1 Java技术 2.2 Mysql数据库 2.3 B/S结构 2.4 SSM框架 第三章 系统分析 3.1 可行性分析 3.1.1 技术可行性 3.1.2 经济可行性 3.1.3 操作可行性 3.2 系统性能分析 3.3 系…

【对角线遍历】python

没啥思路 class Solution:def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:mlen(mat)nlen(mat[0])ret[]if len(mat)0:return retcount0#mn-1是对角线总数while count<mn-1:#x和y的和刚好是count数#偶数为右上走if count%20:xcount if(count<m)else (…

STM32 入门教程(江科大教材)#笔记1

一、GPIO&#xff08;通用输入输出口即I/O口&#xff09; GPIO的基本结构 PA0:引脚1&#xff0c;PA1:引脚2.....PA15:引脚16. 寄存器&#xff1a;一段特殊的寄存器&#xff0c;内核可以通过APB2总线对寄存器进行读写,以完成输出电平和读取电平的功能。 输出寄存器写1&#xf…

期权成交量太小卖不出去怎么办?

今天期权懂带你了解期权成交量太小卖不出去怎么办&#xff1f;在期权交易的世界里&#xff0c;成交量是一个至关重要的指标&#xff0c;它犹如行情的晴雨表&#xff0c;反映着市场的活跃程度。 期权成交量太小卖不出去怎么办&#xff1f; 耐心等待&#xff1a;如果期权合约的流…

论文阅读--CLIP4Clip

CLIP天生适合做retrieve的任务&#xff0c;拿编码好的特征做相似度计算 CLIP做视频的迁移问题在于&#xff0c;一般视频的处理方式是对多个帧做patch&#xff0c;因此得到的图像特征应该是多个帧的融合特征&#xff0c;但CLIP是一个文本特征对应一个图像特征&#xff0c;这时候…

Java进阶学习笔记20——枚举

认识枚举&#xff1a; 枚举是一种特殊的类。 枚举类的格式&#xff1a; 说明&#xff1a; 第一行是罗列枚举的对象名称。只能写合法的标识符&#xff08;名称&#xff09;&#xff0c;多个名称用逗号隔开。 这些名称本质上都是常量&#xff0c;每个变量都会记住枚举类的一个…

从0开始带你成为Kafka消息中间件高手---第三讲

从0开始带你成为Kafka消息中间件高手—第三讲 实际上来说&#xff0c;每次leader接收到一条消息&#xff0c;都会更新自己的LEO&#xff0c;也就是log end offset&#xff0c;把最后一位offset 1&#xff0c;这个大家都能理解吧&#xff1f;接着各个follower会从leader请求同…

FPGA实现多路并行dds

目录 基本原理 verilog代码 仿真结果​ 基本原理 多路并行dds&#xff0c;传统DDS的局限性在于输出频率有限。根据奈奎斯特采样定理&#xff0c;单路DDS的输出频率应小于系统时钟频率的一半。但是在很多地方&#xff0c;要使采样率保持一致&#xff0c;所以&#xff0c;为了…

[Algorithm][动态规划][简单多状态DP问题][按摩师][打家劫舍Ⅱ][删除并获得点数][粉刷房子]详细讲解

目录 1.按摩师1.题目链接2.算法思路详解3.代码实现 2.打家劫舍 II1.题目链接2.算法思路详解3.代码实现 3.删除并获得点数1.题目链接2.算法思路详解3.代码实现 4.粉刷房子1.题目链接2.算法思路详解3.代码实现 1.按摩师 1.题目链接 按摩师 2.算法思路详解 思路&#xff1a; 确…

Mac | Mac 移动硬盘无法分区问题

现象问题 电脑配置&#xff1a;MacBook Pro M1&#xff0c;系统 Sonoma Mac 系统新升级了 Sonoma&#xff0c;结果出现各种问题。外接屏幕居然不能旋转 90 &#xff0c;查了一下是Sonoma系统导致的&#xff0c;以及莫名发热的问题。想着要么回退一下系统算了&#xff0c;于是网…

ICQ 将于 6 月关闭,这是一种奇怪的方式,发现它在 2024 年仍然活跃

你知道ICQ还活着吗&#xff1f;不过&#xff0c;不要太兴奋;它将永远消失。 还记得ICQ吗&#xff1f;如果你这样做了&#xff0c;你可能会记得它是AOL在1998年购买的Messenger客户端&#xff0c;就在Yahoo Instant Messager和MSN Messenger加入竞争的时候。然后Skype出现了&…

Linux--线程的认识(一)

线程的概念 线程&#xff08;Thread&#xff09;是操作系统中进行程序执行的最小单位&#xff0c;也是程序调度和分派的基本单位。它通常被包含在进程之中&#xff0c;是进程中的实际运作单位。一个线程指的是进程中一个单一顺序的控制流&#xff0c;一个进程中可以并发多个线…

Redis内存回收-内存淘汰策略

LFU的访问次数之所以叫做逻辑访问次数&#xff0c;是因为并不是每次key被访问都计数&#xff0c;而是通过运算&#xff1a; 生成0~1之间的随机数R计算 (旧次数 * lfu_log_factor 1)&#xff0c;记录为P如果 R < P &#xff0c;则计数器 1&#xff0c;且最大不超过255访问…

【电路笔记】-二阶滤波器

二阶滤波器 二阶(或双极)滤波器由两个连接在一起的 RC 滤波器部分组成,可提供 -40dB/十倍频程滚降率。 1、概述 二阶滤波器也称为 VCVS 滤波器,因为运算放大器用作压控电压源放大器,是有源滤波器设计的另一种重要类型,因为与我们之前研究过的有源一阶 RC 滤波器一起,…

C++中的指针——指针所占内存空间

提问&#xff1a;指针也是一种数据类型&#xff0c;那么这种数据类型占用多少内存空间呢&#xff1f; 示例 运行结果 示例 运行结果

【引领光子学革命:机器学习与深度学习重塑设计与应用新纪元】

光子器件的逆向设计&#xff1a;利用深度学习技术&#xff0c;可以优化多参数光子器件的设计。通过大量的数据分析和模式识别&#xff0c;深度学习算法能够预测和优化光子器件的性能&#xff0c;从而缩短设计周期并降低设计成本。 超构表面与超材料设计&#xff1a;在新型光学材…

智源联合多家机构推出自动化多样性信息检索评测基准AIR-Bench

智源研究院联合Jina AI、Zilliz、HuggingFace、中国科技大学、中国人民大学、北京邮电大学等多家机构联合推出专门针对检索任务和RAG场景的评测AIR-Bench。AIR-Bench首次提出在检索评测任务中使用LLMs生产评估数据&#xff0c;避免模型过拟合测试数据。同时&#xff0c;由于使用…