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

DP求解 最大连续子数组和

DP求解 最大连续子数组和

题目描述:输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

image-20210823192839901

1. 暴力求解

思路分析:计算数组中每一个连续子数组的和,找出其中最大值

 /*** 暴力求解* @param nums* @return*/public int maxSubArray2(int[] nums){int sum, max = Integer.MIN_VALUE;for (int i = 0; i < nums.length; i++){//每次从头开始加,sum归0sum = 0;for (int j = i; j < nums.length; j++){//每次加一个相当于新的子数组sum += nums[j];//记录最大值if (sum > max){max = sum;}}}return max;}

数据量较小时运行无异常,当数据量过大时,测试将会超时!

2. 动态规划

思路分析:

假设dp[i] 代表以元素 nums[i]为结尾的连续子数组最大和,对于dp[i]的值有两种情况

  • dp[i-1]<=0时,那么**num[i]+dp[i-1]**一定小于num[i]本身,这时如果要求以nums[i]为结尾的连续子数组的最大值,肯定不要其前面的数组,那么dp[i]=nums[i];

    例:[-2,1], 显而易见 dp[0]= -2,那么以1为结尾的连续子数组和,可以是前两者之和 -1 ,也可以只是第二项1,如果是前两者之和,那么肯定小于等于第二项本身(加了个非正数),所以最大肯定为第二项本身,dp[1]=nums[1]=1。

  • dp[i-1]>0时, 那么num[i]+dp[i-1]一定大于num[i]本身,这时如果要求以nums[i]为结尾的连续子数组的最大值,肯定要其前面的数组,那么dp[i]=nums[i]+dp[i-1];

    例:[2,1], 显而易见 dp[0]= 2,那么以1为结尾的连续子数组和,可以是前两者之和 3,也可以只是第二项1,如果是前两者之和,那么肯定大于第二项本身(加了个正数),所以最大肯定为dp[1]=nums[1]+dp[0]=3。

综上:当dp[i-1]<=0时 dp[i]=nums[i]

​ 当dp[i-1]>0时,dp[i]=nums[i]+dp[i-1]

最终构建完dp数组后,其中最大值便是最大连续子数组和

代码如下:

public static int maxSubArray(int[] nums)
{//dp[i] 代表以元素 nums[i]为结尾的连续子数组最大和int[] dp = new int[nums.length];dp[0] = nums[0];for (int i = 1; i < nums.length; i++){//如果dp[i-1]>0,那么加上当前值,将会使当前值增大if (dp[i - 1] > 0){dp[i] = dp[i - 1] + nums[i];}else{//如果dp[i-1]<=0,那么加上当前值,将会使当前值减小(不变),那么还没有本身大,所以直接等于本身即可dp[i] = nums[i];}//以上if判断实际就是找两个的较大值,所以可以直接用下面这个代替//dp[i] = Integer.max(dp[i] = dp[i - 1] + nums[i], dp[i] = nums[i]);}int res = nums[0];//找出dp数组中的最大值for (int i = 1; i < dp.length; i++){if (dp[i] > res){res = dp[i];}}return res;
}

3. 动态规划 优化

优化1:由于dp[i] 只与 dp[i - 1] 和 nums[i] 有关,所以用两个参数存储循环过程中的dp[i]和dp[i-1]的值即可

优化2:之前使用循环找出dp数组中的最大值,可以使用一个max在循环中来记录最大值即可

综上,代码如下

public static int maxSubArray(int[] nums)
{int max = nums[0];//初始情况下最大值为第一个数本身int per = 0;//用于记录dp[i-1]的值,对于dp[0]而言,其前面的dp[-1]=0int cur;//记录当前值for (int num : nums){cur = num;//当前值int curMax = Integer.max(cur, cur + per);//判断前者大,还是当前加上前者大max = Integer.max(max, curMax);//记录最大值per = curMax;//记录当前节元素为尾的最大子数组和}return max;
}

image-20210823203307877

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

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

再生龙clonezilla启动u盘制作,从vmware启动

制作u盘教程&#xff1a; http://www.360doc.com/content/20/0509/22/59153222_911267277.shtml 制作好u盘后&#xff0c;vmware里把u盘添加成硬盘&#xff0c;从u盘所在的硬盘启动即可。...

移动端开发

移动端应用 H5 移动端页面App小程序 移动端开发方式 原生开发&#xff08;Native App&#xff09;网页开发&#xff08;Web App&#xff09;混合开发&#xff08;Hybrid App&#xff09;跨平台移动端框架 跨 App 平台&#xff1a;React Native、weex、Flutter跨 App、小程序、…...

bootstrap table自定义新增行

.deleattrbtn,.addtrbtn{width: 60px;color: #fff;font-size: 12px;background-color: #3177E7;border-radius: 2px;border: 0; }#addtrdiv,#back_addtrdiv{margin: 10px 22px;text-align: right; }.table-bordered{table-layout: fixed;font-size: 12px; }.table th, .table...

毕设系列 -- 基于STM32的人体红外测温枪温度采集系统

文章目录1 简介2 主要器件3 实现效果4 设计原理MLX90614 红外温度传感器5 部分实现代码6 最后1 简介 Hi&#xff0c;大家好&#xff0c;这里是丹成学长&#xff0c;今天向大家介绍一个学长做的单片机项目 基于STM32的人体红外测温枪温度采集系统 大家可用于 课程设计 或 毕业…...

laravel 8 实现excel 导出

composer 下载 composer require maatwebsite/excel 引入 use Elasticsearch\ClientBuilder; 创建excel文件 php artisan make:Exports FangExports FangExports 里面 return Fang::all(); php后台 //导出房东excelpublic function exports(){return Excel::download(…...

Vue相关:

目录 1,说一下vue最大特点是什么或者说vue核心是什么 2,说一下vue常用基本指令有哪些 3,Vue常用的修饰符...

spring-cloud-kubernetes-feign实战

关于spring-cloud-kubernetes spring-cloud-kubernetes是springcloud官方推出的开源项目&#xff0c;用于将Spring Cloud和Spring Boot应用运行在kubernetes环境&#xff0c;并且提供了通用的接口来调用kubernetes服务&#xff0c;主要提供了应用程序使用k8s本身功能&#xff…...

【Unity】如何将资源包里的Prefabs资源为己所用

步骤一、将所需要的prefab从外部导入的资源拖入Scene中。二、右键该预制体&#xff0c;选择Unpack Prefab Completely取消该预制体及其子物体与资源包中预制体的关联。三、将该预制体拖动到自己的prefabs文件夹目录下&#xff0c;制作成自己项目的预制体。四、在Project面板下&…...

防火墙高可靠性

双机热备、BFD双向转发检测、IP-LINK链路检测、Link-Group逻辑组、ETH-Trunk链路捆绑、Bypass&#xff0c;跨数据中心集群&#xff0c;双主控、业务板备份、数据中心会话同步 双机热备 目的&#xff1a;为了防止单点故障 实现&#xff1a;两台硬件软件相同的FW之间通过一条独…...

手写Promise.all()方法

有1个promise报错了&#xff0c;其他的promis会执行吗&#xff1f; 会的&#xff0c;因为Promsie在实例化时候就已经执行完了。手写Promise.all()方法 function PromiseAll(promiseArray){//返回的一定是个proimsereturn new Promise((resolve,reject)>{//首先判断传入的是…...

Centos8.0系统升级到最新版本

一 &#xff0c;Centos8.0更换国内源&#xff08;阿里源&#xff09; 1&#xff0c; 备份旧的配置文件 mv /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.backup2&#xff0c;进入cd /etc/yum.repos.d cd /etc/yum.repos.d3&#xff0c;下载新的 Ce…...

高端音响的死亡被大大夸大了

几年前&#xff0c;在 MP3 盗版时代的鼎盛时期——当高端音频世界哀叹 MP3 文件的糟糕音质&#xff0c;而 MP3 用户乐于用音质换取免费音乐时——一位业内同事问我我以为高端音频已经死了。我向她保证不&#xff0c;一部分音乐迷&#xff0c;虽然可能不是主流&#xff0c;但总是…...

Java学习笔记--13.网络编程

Java学习笔记–13 第十章 网络编程 目录Java学习笔记--13前言网络编程1.定义2.TCP通信(1).ServerSocket(2).Socket3.UDP通信(1).发送方(2).接收方前言 21世纪&#xff0c;走进了信息时代&#xff0c;各种各样的软件层出不穷&#xff0c;但是总离不开程序开发&#xff0c;离不…...

python100例045求1-100之和用sum(range(1,101))

""" 题目045&#xff1a;统计 1 到 100 之和 """ def test045():count 0for i in range(1, 101):count iprint(count)# 二print(sum(range(1, 101))) test045()...

PyScreeze 基本使用(1)

PyScreeze 基本使用&#xff08;1&#xff09; PyScreeze屏幕截图 PyScreeze是Python 2和3的一个简单的跨平台屏幕截图模块。 关于 PyScreeze可以拍摄截图&#xff0c;将它们保存到文件中&#xff0c;并在屏幕中定位图像。这是有用的&#xff0c;如果你有一个小的图像&#x…...

wimform 继承窗体卡顿解决

get { const int CS_NOCLOSE 0x200; CreateParams cp base.CreateParams; cp.ClassStyle cp.ClassStyle | CS_NOCLOSE; if (!DesignMode) { cp.ExStyle...

git 替换commit的账户与邮箱信息 GitLab: Committer‘s email does not follow the pattern

最终解决方法来源&#xff1a; https://segmentfault.com/q/1010000006999861 https://www.cnblogs.com/zh7791/p/12986083.html ① git rebase -i HEAD~N N代表前N次的提交记录 ② 出现记录后键入i进入INSERT模式&#xff0c;在需要修改的条目上&#xff0c;将pick改为edit…...

后端返回状态码401, 获取不到怎么办?

传送门...

解决for循环中异步请求顺序不一致的问题

解决for循环中异步请求顺序不一致的问题参考文章&#xff1a; &#xff08;1&#xff09;解决for循环中异步请求顺序不一致的问题 &#xff08;2&#xff09;https://www.cnblogs.com/mo3408/p/12163012.html 备忘一下。...

2021-08-23 arm开发板上执行程序报错:-sh: ./uart_app: No such file or directory

问题前提描述: 使用的是正点原子 arm alpha 开发板存在这个文件 其他相关问题: 刚出现这个问题时,我在csdn上搜到的其他造成原因: “doc格式(windows系统)、mac(苹果系统)在上传到xshell(unix系统)后, unix系统是不支持doc&#xff08;mac&#xff09;格式的” 如果是这种情况…...

element时间选择器 选择当前时间和之后的时间

<el-form-item label"称号有效期&#xff1a;" prop"featureEndTime"><el-date-pickerv-model"formObj.featureEndTime"type"datetime"placeholder"选择日期"format"yyyy-MM-dd HH:mm:ss"value-format&q…...

Dubbo(一)项目架构演变过程

Dubbo&#xff08;一&#xff09;项目架构演变过程架构演变过程单体架构垂直架构SOA&#xff08;分布式架构&#xff09;微服务架构架构演变过程 dubbo是一款高性能的java rpn框架。 随着互联网的发展&#xff0c;用户群体逐渐壮大&#xff0c;网站的流量成倍增长&#xff0c;…...

搜索: DFS + 剪枝:木棒

题目链接&#xff1a;https://www.acwing.com/problem/content/169/ 题目&#xff1a; 乔治拿来一组等长的木棒&#xff0c;将它们随机地砍断&#xff0c;使得每一节木棍的长度都不超过 50 个长度单位。 然后他又想把这些木棍恢复到为裁截前的状态&#xff0c;但忘记了初始时有…...

PMP项目管理 | 项目整合管理

PMP项目管理之项目整合管理项目整合管理定义及概念项目整合管理考虑要素项目整合管理过程包括子过程分解4.1 制定项目章程定义理解作用发生时机参与方输入、工具与技术和输出4.2 制定项目管理计划定义理解作用发生时机参与方项目管理计划和文件输入、工具与技术和输出4.3 指导和…...

2021-08-23 linux的部分基本命令与vi/vim的部分命令

linux的基本命令 文章目录linux的基本命令前言一、APT(Advanced Packing Tool)1.工作原理2.修改源3.几个常用的命令二、vi/vim一. vi/vim 模式1.vi有两种工作模式二. vi/vim 命令1.vim:退出命令2.vim删除与修改命令3.vim拷贝与粘贴命令4.vim 撤销命令5.vim 搜索命令6.vim 替换命…...

关于POST接口返回图片流,前端展示图片

工作当中&#xff0c;有时候会碰到后端由于存储方式等原因&#xff0c;返回给前端的图片的请求方式为POST&#xff0c;这个时候前端如果需要把图片显示在页面上&#xff0c;就要把图片流转换为图片&#xff1a; post返回的图片流&#xff0c;在chrome的network preview时是一个…...

方法与方法重载介绍

1- 方法介绍 定义&#xff1a; 方法是一段具有独立功能的代码块&#xff0c;不调用就不执行。 好处&#xff1a; ①能够提高代码的复用性&#xff08;一个方法可以调用好多次&#xff09;&#xff0c; ②提高代码的可读性&#xff0c;对代码进行分类管理 注意&#xff0c; …...

demo随笔

在我们做项目时&#xff0c;有时候总是会引用到其他的资源&#xff0c;这时候就需要使用iframe来进行引用&#xff0c;那引用之后父页面和子页面要咋进行通信呢&#xff0c;今天遇到一个需求是这样子的&#xff1a;在vue里面嵌入了cesium的地球&#xff0c;地球是第三方做的&am…...

大数据技术hadoop核心Flume

大家好&#xff0c;我是曜耀。 这几天曜耀开始复习一下自己的专业课&#xff0c;相信看过的都了解&#xff0c;就是当前热门的大数据技术与应用。我对于这门专业来说&#xff0c;一个特色就是都会&#xff0c;你说Linux我懂&#xff0c;你说java这是基操&#xff0c;python不好…...

HDU 1536 S-Nim

1536 #include<bits/stdc.h> using namespace std; int s[110],sg[10010]; int k; int SG(int x){if(sg[x]!-1)return sg[x];bool vis[110];memset(vis,0,sizeof(vis));for(int i0;i<k;i){if(x>s[i]){SG(x-s[i]);vis[sg[x-s[i]]]1;}}for(int i0;;i){if(!vis[i]){...

dbc2000 注册机|dbc2000 注册码注册机下载

点击下载来源&#xff1a;dbc2000 注册机 dbc2000 注册机是同名源程序软件的注册机软件&#xff0c;该源程序软件是一款应用于数据库搭建以及数据写入的数据库架设工具&#xff0c;它拥有强大的数据写入功能&#xff0c;在作为应用程序使用时&#xff0c;它不仅可以充当数据属性…...

秋招面经第八弹:网易二面-数据开发工程师

秋招第八弹&#xff1a;网易二面-数据开发工程师 写在最前&#xff1a;秋招以来一直在冲&#xff0c;因为事情比较多&#xff0c;对于笔试面试一直没有复盘&#xff0c;现在靠仅存的记忆把面试的一些问题记录下来&#xff0c;尽可能记录出能回忆到的问题&#xff0c;但可能记的…...

安卓课程格子APP

https://download.csdn.net/download/weixin_57836618/73810452 功能演示&#xff1a; 查看所有课程 点击主页面空白处即可添加课程 添加课程之后查看课程 查看双周课程 查看单周课程 6.查看课程详情...

强化学习——格子世界

强化学习——格子世界 项目源码地址&#xff1a;https://gitee.com/infiniteStars/machine-learning-experiment 1. 实验内容 2. 实验代码 import numpy as np import matplotlib.pyplot as plt from matplotlib.table import Table from xml.dom.minidom import Document #手…...

华为机试 - 跳格子游戏

目录 题目描述 输入描述 输出描述 用例 题目解析 算法源码 题目描述 地上共有N个格子&#xff0c;你需要跳完地上所有的格子&#xff0c;但是格子间是有强依赖关系的&#xff0c;跳完前一个格子后&#xff0c;后续的格子才会被开启&#xff0c;格子间的依赖关系由多组st…...

php 爬课程表信息,Ruby爬取教务系统生成课程表

我为什么要虐自己最近觉得课程格子广告越来越多&#xff0c;乱七八糟的东西越来越多&#xff0c;完全失去了一开始的存在价值&#xff0c;并且没有电脑端app&#xff0c;想查看课程必须拿出手机&#xff0c;而我使用电脑频率要比手机高&#xff0c;所以才有了折腾的动力。于是我…...

android 课程表 ui,UICollectionViewLayout实现课程表布局

因为项目中有课程表的相关模块&#xff0c;第一时间想到用UICollectionView。然而后期的需求越来越复杂&#xff0c;每个格子需要展示的内容越来越多&#xff0c;所以不得不寻找合适的解决方案。最后发现自定义UICollectionViewLayout可以实现我的需求。先放效果图&#xff1a;…...

Android自定义View课程表,Android 自定义View课程表表格

自己闲下来时间写的一个课表控件使用的自定义LinearLayout 里面View都是用代码实现的 最终效果如下图 写的可能有问题希望多多指点创建一个自定义LinearLayout 控件用来装载课程的信息和课程的周数 和节数大概的布局三这样的根据上面的看来觉得总体布局我分了两个 上面的星期是…...

java课程设计设计_java课程设计

1. 团队课程设计博客链接https://www.cnblogs.com/choco1ate/p/12172223.html2.本组课题及本人任务本组课题&#xff1a;泡泡堂(炸弹人)游戏本人任务&#xff1a;Box类(游戏地图中的每个方格)Bomb类(游戏过程中的)游戏玩家输赢信息的文件储存3.需求分析Box类&#xff1a;该类为…...

《课程格子》的一个笔试题目

题目如下&#xff0c;感觉很适合喜欢琢磨的程序员&#xff0c;也是考验你编码风格的时候。 Lets make a tower defense game&#xff08;塔防游戏):1. You have 1 tower, with H health and D dps(damage per second).2. There are n attackers, each with h_i health and d_i …...

Android仿照超级课程表 or 课程格子 一键提取课表功能(方正系统)

参考文章http://blog.csdn.net/sbsujjbcy ,本文仿照‘ 安卓弟 提供的android 项目实战——打造超级课程表一键提取课表功能文章&#xff0c;对他的代码进行了修改和补充&#xff0c;为什么要修改呢&#xff1f;原因是安卓弟的那个源码版本过于老旧&#xff0c;很多方法已经过…...

专用计算机数控编程软件,数控车床编程app

数控车床编程软件介绍数控车床编程是一款很好使用的编程和图形绘制的结合工具&#xff0c;数控车床编程功能强大&#xff0c;可以更加简单轻松的制作出编程和二位制图相结合帮助用户更快的提升了工作效率和促进团队合作。同时具有cad导入图形功能&#xff0c;具有完美的曲线编程…...

计算机控制面板程序可以设置鼠标,外设门诊:游戏中如何使用鼠标宏提升操作...

1网友关于鼠标宏的奇怪提问[中关村在线键鼠频道原创]用户及玩家在日常使用键鼠外设产品时&#xff0c;经常会出现这样或那样的问题。小到驱动下载安装&#xff0c;大到更换线材、MOD改造等等&#xff0c;如果您想得到及时丰富的解答&#xff0c;请到电竞游戏装备区论坛》发帖&a…...

Win10鼠标宏怎么设置?电脑设置鼠标宏的方法

鼠标宏集成鼠标本身的作用&#xff0c;将多个操作指令集成起来&#xff0c;也就是利用鼠标自动完成一系列批量操作。这个操作你可以自由发挥想象。近期有很多Win10用户都在问鼠标宏怎么设置&#xff1f;其实设置方法很简单&#xff0c;下面小编就来给大家分享一下电脑重装系统后…...

计算机cf编程,警察牧马人宏自定义编程计算机游戏鼠标有线大声笑/ cf英雄联盟光速质量保证....

原因1: 支持7键全键自定义宏编程&#xff0c;以满足各种游戏设置功能(鼠标全键支持自定义宏设置&#xff0c;可以通过鼠标软件设置键盘自定义&#xff0c;以及任意键的功能设置)&#xff1b; <原因2: 宏编程软件流行的游戏宏&#xff0c;没有繁琐的操作&#xff0c;一键设置…...

java实现鼠标宏编程_对键盘鼠标宏处理--按键精灵让我们不要重复工作

对键盘鼠标宏处理&#xff0d;&#xff0d;按键精灵让我们不要重复工作更新时间&#xff1a;2006年12月29日 00:00:00 作者&#xff1a;每天&#xff0c;我们开机的第一件事就是打开Foxmail收信&#xff0c;然后打开QQ看看好友的留言……&#xff0c;但每天都重复这些固定的操…...

如何在计算机设置鼠标宏,游戏鼠标宏设置是什么?怎么设置游戏鼠标宏?

有对游戏已经电脑配件研究过的用户就知道&#xff0c;通过鼠标宏比较容易达到武器射速上限&#xff0c;对于手速较慢的人来说是一个不错的选择。鼠标宏并不是挂&#xff0c;是不会被封号的&#xff0c;所以可以放心使用。对于老玩家来说&#xff0c;鼠标宏确实很给力&#xff0…...

双11盛宴之下,AI正在成为新零售生态关键一环

大幕拉开&#xff0c;灯光音效就位&#xff0c;零售市场的最华丽舞台剧又将上演。 双11盛宴年年如约而至&#xff0c;但十年过去&#xff0c;如今的双11已经由性价比第一&#xff0c;变成了体验为王。消费习惯由单纯的便宜&#xff0c;开始向重视新技术、新场景&#xff0c;注…...

智能音箱中国淘汰赛:从百箱大战到三足鼎立

转载自PingWest品玩&#xff08;ID&#xff1a;wepingwest&#xff09;2019 年 2 月 18 日&#xff0c;36Kr 引援知情人士报道&#xff0c;腾讯首款自研智能音箱项目“听听音箱”已经暂停。这个项目原属移动互联网事业群&#xff08;MIG&#xff09;&#xff0c;后来在腾讯组织…...

从C2C到CFC再到C2W,中国互联网来到第三阶段

小度在2019年一季度首拿中国智能音箱市场出货量第一&#xff0c;行业有一种看法是&#xff1a;小度一季度登顶与百度春晚营销活动及价格促销有直接相关&#xff0c;小度二季度如果能保持冠军地位&#xff0c;才能体现出真实的市场实力。5月&#xff0c;罗超频道在对百度副总裁、…...