浙大数据结构网课第一周入门

news/2024/4/24 23:22:20/

题目详情

Given a sequence of K integers { N1​, N2​, ..., NK​ }. A continuous subsequence is defined to be { Ni​, Ni+1​, ..., Nj​ } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

代码长度限制

16 KB

时间限制

200 ms

内存限制

64 MB

简单翻译:

对于给定数组,不仅要找到最大子序和,还要找到最大子序和对应的开头与结尾的元素,其中如果数组全是负数就返回0与锁哥数组的开头与结尾元素

第一次写错误:

(1)要求的是最大子序和对应的开头与结尾的元素,一开始就返回的是下标

(2)没有看清如果数组全是负数就返回0与锁哥数组的开头与结尾元素

(3)没有考虑好如果数组全是负数与数组里只有负数和0的情况

代码实现:

#include <iostream>
#include <limits.h>
using namespace std;
int main(void) {int K;cin >> K;int a[K];for(int i = 0; i < K; i++) {cin >> a[i];}int maxSum = INT_MIN; int sum = 0;int end = 0, maxEnd = 0;int start = 0, maxStart = 0;for(int i = 0; i < K; i++) {sum += a[i];end = i;if(sum < 0) {sum = 0;end = start = i + 1;}else {if(maxSum < sum) {maxSum = sum;maxEnd = end;maxStart = start;}}}if(maxSum == INT_MIN) {    //如果maxSum还是INT_MIN,说明数组里全是负数cout << 0 << ' ';cout << a[0] << ' ';cout << a[K - 1] << endl;}else {cout << maxSum << ' ';cout << a[maxStart] << ' ';cout<< a[maxEnd] << endl;        }
}

题目详情

给定K个整数组成的序列{ N1​, N2​, ..., NK​ },“连续子列”被定义为{ Ni​, Ni+1​, ..., Nj​ },其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下:

  • 数据1:与样例等价,测试基本正确性;
  • 数据2:102个随机整数;
  • 数据3:103个随机整数;
  • 数据4:104个随机整数;
  • 数据5:105个随机整数;

输入格式:

输入第1行给出正整数K (≤100000);第2行给出K个整数,其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。

输入样例:

6
-2 11 -4 13 -5 -2

输出样例:

20

思路一:贪心

时间复杂度O(N)

代码实现:

#include <iostream>
using namespace std;
int main(void) {int K;cin >> K;int num[K];for(int i = 0; i < K; i++) {cin >> num[i];}int sum = 0;int maxSum = 0;for(int i = 0; i < K; i++) {sum += num[i];if(sum < 0) {sum = 0;}else {if(sum > maxSum) {maxSum = sum;}}}cout << maxSum;return 0;
}

 

 思路二:递归分治

主要思路:

1. 将序列从中间分为左右两个序列

2. 递归求得两子列的最大和sumLeft与sumRight

3.从中分点向左右扫描找到跨过分界线的最大子列和sumMiddle

4.取最大值

实际操作时递归三部曲:

1.参数与返回值:

参数:num数组,返回当前子列和最大值

2.终止条件:

左右端点重合

3.单层递归逻辑:

单纯左侧与单纯右侧简单,难的是跨中间点

跨中间点其实也用到了贪心的想法,即分成两部分,分别找左[left, middle]与右[middle + 1, right]的最大值,然后加起来就是跨中间点最大值

代码实现 

#include <iostream>
#include <vector>
using namespace std;
int layer = 0;
int Max3(int A, int B, int C) { //这个函数是用来比较左中右里最大值return A > B ? A > C ? A : C : B > C ? B : C;/* A > B ? A > C ? A : C :这一部分首先判断 A 是否大于 B,如果是,则继续判断 A 是否大于 C,如果是,则返回 A,否则返回 C。如果 A 不大于 B,则执行下一个部分:B > C ? B : C这一部分首先判断 B 是否大于 C,如果是,则返回 B,否则返回 C。*/
}
int findMaxMiddleSum(vector<int> &num, int left, int right, int middle) {   //这个函数是用来找“中”(跨越中间分界点)的最大值int leftSideSum = 0, leftSideMaxSum = 0;for(int i = middle; i >= left; i--) {leftSideSum += num[i];if(leftSideSum > leftSideMaxSum) {leftSideMaxSum = leftSideSum;}}int rightSideSum = 0, rightSideMaxSum = 0;for(int i = middle + 1; i <= right; i++) {rightSideSum += num[i];if(rightSideSum > rightSideMaxSum) {rightSideMaxSum = rightSideSum;}}return leftSideMaxSum + rightSideMaxSum;
}
int recursion(vector<int> &num, int left, int right) {//递归终止条件
//    cout << "left = " << left << endl;
//    cout << "right = " << right << endl;
//    cout << "layer = " << ++layer << endl;if(left == right) {if(num[left] > 0) {return num[left];}else return 0;}//单层递归逻辑int middle = (left + right) / 2;
//    cout << "middle = " << middle << endl;int leftSum = recursion(num, left, middle);int rightSum = recursion(num, middle + 1, right);int middleSum = findMaxMiddleSum(num, left, right, middle);return Max3(leftSum, rightSum, middleSum);
}
int main(void) {int K;cin >> K;vector<int> num(K, 0);for(int i = 0; i < K; i++) {cin >> num[i];}
//    for(int i = 0; i < K; i++) {
//        cout << num[i] << " ";
//    }
//    cout << endl;
//    cout << "-------------------------" << endl;int maxSum = recursion(num, 0, K - 1);cout << maxSum;return 0;
}

时间复杂度分析:

N代表长度

N = 2 ^ k

k = logN

T(N) = N * O(1) + c * O(NlogN)

空间复杂度 

递归的空间复杂度=递归深度*每次递归的空间复杂度。每次递归边界变为一半,最后结束递归时N/2^k=1,递归深度k=log2 N,S(N)=O(NlogN)


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

相关文章

SSH连接本地centerOS系统配置

SSH连接本地linux系统 前提&#xff1a;安装好centerOS系统并能启动 目标&#xff1a;连通外网并设置SSH 1.网卡配置文件路径 打开linux本地终端 快捷键一般是ctrlaltf2(f1~f3) 这里是管理员登录,密码是隐藏式的输入(输入看不见) 这样就显示成功登录了&#xff01; 下面查…

屏幕亮度调节工具:Simple Screen Shade Mac

Simple Screen Shade Mac版是mac上一款优秀的屏幕颜色亮度调节工具&#xff0c;能够让我们Mac电脑的显示器背景变暗&#xff0c;这样可以保护你眼睛的健康并保持舒适。Simple Screen Shade 旨在实现最大程度的简单性和易用性。你可以设置灰色背景以减轻明亮鲜艳的色彩&#xff…

Pandas入门实践2 -数据处理

为了准备数据进行分析&#xff0c;我们需要执行数据处理。在本节中&#xff0c;我们将学习如何清理和重新格式化数据&#xff08;例如&#xff0c;重命名列和修复数据类型不匹配&#xff09;、对其进行重构/整形&#xff0c;以及对其进行丰富&#xff08;例如&#xff0c;离散化…

Laravel使用JWT

开始安装jwt &#xff08;本次安装不建议直接在项目中安装及使用&#xff09; 1.composer 安装jwt composer require tymon/jwt-auth 1.0.0-rc.1 2.在config 文件夹的app.php 中注册服务提供者 providers > [Tymon\JWTAuth\Providers\LaravelServiceProvider::class, ]…

使用计算机视觉实战项目精通 OpenCV:6~8

原文&#xff1a;Mastering OpenCV with Practical Computer Vision Projects 协议&#xff1a;CC BY-NC-SA 4.0 译者&#xff1a;飞龙 本文来自【ApacheCN 计算机视觉 译文集】&#xff0c;采用译后编辑&#xff08;MTPE&#xff09;流程来尽可能提升效率。 当别人说你没有底线…

01、Cadence使用记录之新建工程与基础操作(原理图绘制:OrCAD Capture CIS)

01、Cadence使用记录之新建工程与基础操作&#xff08;原理图绘制&#xff1a;OrCAD Capture CIS&#xff09; 硕士学电磁场去了&#xff0c;写点博客记录下学习过程。 参考的教程是B站的视频&#xff1a;allegro软件入门视频教程全集100讲 本科的时候就对Cadence有所耳闻&am…

docker问题集锦

1.http: server gave HTTP response to HTTPS client sudo vim /etc/docker/daemon.json 添加{“insecure-registries”: [“ip:端口”]} sudo service docker restart 无效 sudo vim /lib/systemd/system/docker.service 在ExecStart最后添加 --insecure-registry ip:端口 sud…

GDB调试实验

一、实验准备 在 Linux 环境软件开发中&#xff0c;GDB 是调试 C 和 C 程序的主要工具。本次实验围绕着GDB常用的调试操作进行。 1、设置断点的意义 当我们想查看变量内容&#xff0c;堆栈情况等等&#xff0c;可以指定断点。程序执行到断点处会暂停执行。break 命令用来设置…

亚马逊、ebay、temu如何提升产品点击率?测评自养号解析

产品点击率对于店铺销售额的影响至关重要&#xff0c;尤其是在竞争越来越激烈的市场环境中&#xff0c;想要有销量和转化&#xff0c;提高产品listing点击率成为了非常关键的一环。 1. 产品主图 顾客浏览产品时&#xff0c;第一眼看到的就是主图&#xff0c;一张优质的主图更容…

什么是MVVM?

MVVM 是 Model-View-ViewModel 的缩写&#xff0c;是M-V-VM三部分组成。它本质上就是MVC的改进版。 M&#xff1a;Model 代表数据模型&#xff0c;也可以在Model中定义数据修改和操作的业务逻辑。 V&#xff1a;View 代表视图UI&#xff0c;它负责将数据模型转化成UI 展现出来。…

材料科学基础学习指导-吕宇鹏-名词和术语解释-第5章:相图

目录 第一部分 第二部分​​​​​​​ 第三部分 第四部分​ 第一部分 1.1组元&#xff1a;是材料科学中的基本术语。意思是组成合金的独立的、最基本的单元。 1.2相&#xff1a; 指合金中具有同一聚集状态、同一晶体结构和性质并以界面相互隔开的均匀组成部分。​​​​…

api数据接口文档_接口文档示例(Taobao/jd/pinduoduo/开放接口调用)

api数据接口文档_接口文档示例 本文主要是提供了一个接口文档的范文&#xff0c;内容修订历史、目录、时序图、接口要素描述、接口说明、使用示例、字典、FAQ。 使用MD格式文档&#xff08;makedown&#xff09;&#xff0c;选择原因&#xff0c;容易格式转换&#xff0c;开发…

LeetCode238. 除自身以外数组的乘积

238. 除自身以外数组的乘积 描述示例解题思路解法1(最最暴力求解&#xff0c;但不符合要求)解法2(暴力求解&#xff0c;也不符合要求&#xff0c;但时间复杂度O&#xff08;N))解法3(最优解&#xff0c;符合题意&#xff0c;时间复杂度O(N)) 描述 给你一个整数数组 nums&#…

Linux的.serivice文件介绍

一、什么是.service文件&#xff1f; linux中.servic文件是服务的配置文件&#xff0c;通过systemctl进行操作。存放位置&#xff1a;/usr/lib/systemd/system 二、配置说明 通常在&#xff0c;service配置文件中包含三个部分&#xff0c;分别为&#xff1a; 一、[Unit]:控制部…

创造rap一首,关于毕业论文难写,导师不负责

Verse1: 毕业季节&#xff0c;任务繁重 毕业论文&#xff0c;压力倍增 想着论文顺利&#xff0c;却被教授推脱 努力攀登高峰&#xff0c;却是一场空 Chorus: 毕业论文难写&#xff0c;导师不负责 对论文监督&#xff0c;一筹莫展 毕业论文难写&#xff0c;难缠之处 摆脱麻烦&am…

Unity记录3.5-地图-第三阶段总结

文章首发及后续更新&#xff1a;https://mwhls.top/4493.html&#xff0c;无图/无目录/格式错误/更多相关请至首发页查看。 新的更新内容请到mwhls.top查看。 欢迎提出任何疑问及批评&#xff0c;非常感谢&#xff01; 汇总&#xff1a;Unity 记录 摘要&#xff1a;柏林噪声与 …

Linux -- 进阶 Web服务器 基础前瞻( 二 )

WWW服务器的类型 &#xff1a; 静态网站 官方 &#xff1a; 仅提供用户浏览的单向静态网页&#xff0c;单纯是由服务器单向提供数据给客户端&#xff0c;Server 不 需要与client 端有互动&#xff0c;可以浏览网站&#xff0c;但是无法数据上传。 ( 说白就是 服务器提供的…

C++并发锁相关并发

互斥锁mutex #include <mutex> {std::mutex mtx;mtx.lock();// do somethingmtx.unlock(); } mutex成员方法&#xff1a;lock()、try_lock()、unlock() try_lock&#xff1a; 1&#xff09;所有线程都没有lock时&#xff0c;调用lock&#xff0c;并返回true&#xff1b;…

鉴智机器人重磅发布双目智驾解决方案,新一代全系智驾产品线亮相上海车展

4月18日&#xff0c;以「拥抱汽车行业新时代」为主题的2023上海车展正式拉开帷幕。以视觉3D理解为核心的下一代自动驾驶系统提供商鉴智机器人&#xff0c;携全新升级的智驾产品线首次亮相车展&#xff0c;重磅发布基于AI的双目立体视觉智驾方案。 凭借双目立体视觉系统的差异化…

Event Camera (事件相机)

1.传统相机的缺点 1.随着计算机视觉领域的不断发展&#xff0c;目标检测的算法也越来越多样化&#xff0c;特别是近些年深度学习在计算机视觉领域的进步&#xff0c;已经产生了很多优秀的目标检测方法&#xff0c;这些基于帧的方法对于图片的质量有一定的要求&#xff0c;比如合…