最大尺寸和问题描述为，在n个整数(包含负数)的数组A中，求之和最大的非空连续子数组如..

2021年上半年上午试卷综合知识

第 40 题


知识点	数组
关键词	时间复杂度数组算法子段
章/节	计算机软件知识

最大尺寸和问题描述为，在n个整数(包含负数)的数组A中，求之和最大的非空连续子数组,如数组A=(-2,11,-4,13,-5,-2) ，其中子数组B=(11,-4,13)具有最大子段和20(11-4+13=20) 。求解该问题时,可以将数组分为两个n/2个整数的子数组最大子段或或者在前半段,或者在后半段,或者跨越中间元素,通过该方法继续划分问题,直至最后求出最大子段和,该算法的时间复杂度为( )。

A. O(nlgn)

B. O(n²)

C. O(n²lgn)

D. O(n³)

相关试题计算机软件知识

第36题

2023年上半年

在软件系统交付给用户使用后，为了使用户界面更友好，对系统的图形输出进行改进，该行为属于（）维护。

第53题

2011年下半年

第3题

2022年上半年

为了实现多级中断,保存程序现场信息最有效的方法是使用()。

知识点讲解

· 数组

数组

数组的定义及基本运算

n维数组是一种"同构"的数据结构，其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。

数组结构的特点是：数据元素数目固定；数据元素具有相同的类型；数据元素的下标关系具有上下界的约束且下标有序。

对数组进行的基本运算有以下两种。

（1）给定一组下标，存取相应的数据元素。

（2）给定一组下标，修改相应的数据元素中某个数据项的值。

数组的顺序存储

一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。

由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。对二维数组有两种存储方式：一种是以列为主序的存储方式；另一种是以行为主序的存储方式。

设每个数据元素占用L个单元，m、n为数组的行数和列数，那么以行为主序优先存储的地址计算公式为

Loc(a_ij)=Loc(a₁₁)+((i-1)n+(j-1))L

同样的，以列为主序优先存储的地址计算公式为

Loc(a_ij)=Loc(a₁₁)+((j-1)m+(i-1))L

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5