每日一题——连续子数组的最大和

news/2024/11/7 14:08:10/

题目


输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,子数组最小长度为1。求所有子数组的和的最大值。

数据范围:1<=n<=2×105 −100<=a[i]<=100

要求:时间复杂度为 O(n),空间复杂度为 O(n)

示例1

输入:
[1,-2,3,10,-4,7,2,-5]
返回值:
18
说明:
经分析可知,输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2

输入:
[2]
返回值:
2

思路


这题属于动态规划,可以使用状态转移方程求得子数组的最大值。

  • 用dp数组表示以下标i为终点的最大连续子数组和。
  • 遍历数组,每次遇到一个新的数组元素,连续的子数组要么加上变得更大,要么这个元素本身就更大,就可以舍弃之前的子数组。状态转移方程为dp[i]=max(dp[i−1]+array[i],array[i])。
  • 维护一个最大值记录当前已经得到的最大和的值。

解答代码


#include <algorithm>
#include <vector>
class Solution {
public:/*** @param array int整型vector * @return int整型*/int FindGreatestSumOfSubArray(vector<int>& array) {// write code hereif (array.empty()) {return 0;}auto size = array.size();vector<int> dp(size, 0);dp[0] = array[0];int max_sum = dp[0];for (int i = 1; i < size; i++) {//状态转移方程dp[i] = max(dp[i-1] + array[i], array[i]);//记录最大值max_sum = max(dp[i], max_sum);}return max_sum;}
};

http://www.ppmy.cn/news/1042013.html

相关文章

如何在HTML中使用React

突发奇想 查了查真的可以,官方文档: 在网站中添加 React – React 开始 引入js <!-- 开发环境使用 --><script src"https://unpkg.com/react18/umd/react.development.js"></script><script src"https://unpkg.com/react-dom18/umd/reac…

openEuler上安装19c单机的问题集

1、欧拉的版本 仅在openEuler release 20.03版本上安装成功 2、oracle用户crontab没权限 orcl:/home/oracledb> crontab -l You (oracle) are not allowed to use this program (crontab) See crontab(1) for more information 处理办法&#xff1a;# echo oracle >&…

Richtek(立锜)车载PD快充产品常见问题解答—兼具 USB PD 和 UFCS 快充电源完整解决方案

1 我的Switch游戏机能不能用最新的PD协议&#xff1f; 可以的&#xff0c;PD最新协议都兼容旧协议 2 PD协议向下兼容吗&#xff1f; 是的&#xff0c;PD3.1也是向下兼容的 3 UFCS协议目前用什么仪器测试&#xff1f; 谢谢。 目前RICHTEK有协议测试工具&#xff0c;中国UFCS协…

一些面向H5画布Canvas的js库

1. Three.js&#xff08;三维库&#xff09; 一个强大的JavaScript 3D库&#xff0c;可以创建复杂的三维场景和动画。中文名称为“三维库”。 <script src"https://cdn.bootcdn.net/ajax/libs/three.js/0.151.3/three.min.js"></script>2. Babylon.js&…

C++ Primer Plus 第6版 读书笔记(10) 第十章 类与对象

第十章 类与对象 在面向对象编程中&#xff0c;类和对象是两个重要的概念。 类&#xff08;Class&#xff09;是一种用户自定义的数据类型&#xff0c;用于封装数据和操作。它是对象的模板或蓝图&#xff0c;描述了对象的属性&#xff08;成员变量&#xff09;和行为&#xf…

OJ练习第150题——分割回文串

分割回文串 力扣链接&#xff1a;131. 分割回文串 题目 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 示例 Java代码 class Solution {List<List…

Vue3.X 创建简单项目

一、环境安装与检查 首先&#xff0c;我们要确保我们安装了构建vue框架的环境&#xff0c;不会安装的请自行百度&#xff0c;有很多安装教程。检查环境 node -v # 如果没有安装nodejs请安装&#xff0c;安装教程自行百度 vue -V# 没有安装&#xff0c;请执行npm install -g v…

策略梯度方法

策略梯度方法 数学背景 给定一个标量函数 J ( θ ) J\left(\theta\right) J(θ)&#xff0c;利用梯度上升法&#xff0c;使其最大化&#xff0c;此时的 π θ \pi_\theta πθ​就是最优策略。 θ t 1 θ t α ∇ θ J ( θ t ) \theta_{t1}\theta_t\alpha \nabla_\theta…