浙大数据结构自用笔记(1)--基本概念和最大子列和算法问题_7-3 最大子列和问题分数 50作者 ds课程组单位 浙江大学给定k个整数组成的序列{ n-程序员宅基地

技术标签: 数据结构  

基本概念

题目:求最大子列和问题:

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

算法一:暴力求子列
/*
目的->求最大子列和:

    时间复杂度:O(N^3)
    时间:  0.058 s
*/
#include<stdio.h>
int MaxSubseqSum1(int A[ ], int N)
{
   
    
    int ThisSum, MaxSum = 0;
    int i, j, k;
    for (i=0; i<N; i++)      //i为子列的左端位置
    {
   
    
        for (j=i; j<N; j++)   //j为子列的右端位置
        {
   
    
            ThisSum = 0;      //ThisSum是A[i]到A[j]的子列和
            //k的循环没有必要,有很多重复计算
            for (k=i; k<=j; k++) //实现从A[i]到A[j]的累加
                ThisSum += A[k];
            if (ThisSum > MaxSum) //如果新的子列和更大
                MaxSum = ThisSum; //则更新结果
        }
    }
    return MaxSum;
}
int main(void)
{
   
    
    int a[6] = {
   
    -2, 11, -4, 13, -5, -2};
    int MaxSum;
    MaxSum = 
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Ghost_zyl/article/details/103102780

智能推荐

原型设计八大原则-程序员宅基地

文章浏览阅读4k次,点赞2次,收藏6次。原型设计八大原则 原则一:了解受众和意图这是原型设计流程的第一条,也是至关重要的原则。了解受众并理解圆形的意图,能驱动原型设计流程的各个方面,原则二:稍加规划——再做原型稍加规划,再做原型,以渐增、迭代的方式展开工作,这样能适应不断变化的环境。原则三:设定期望设定期望是基于名为激发心理学方法原则四:可以画草图在这些决定往往归根于第一个原则:了解受众和意图原则五:是原型,不是蒙娜丽莎原形本质上是最终产品的不完善和粗略的版本,原型并不完美,事实上粗略的原型往往能获得更好的反馈。原则六:如果做不出来原形_原型设计

Qt QVariant 的 default-constructed values_qt default-constructed-value-程序员宅基地

文章浏览阅读222次。The documentation of certain container class functions refer to default-constructed values; for example, QVector automatically initializes its items with default-constructed values, and QMap::value() returns a default-constructed value if the specified key_qt default-constructed-value

Java文件类boolean isHidden()方法(带示例)-程序员宅基地

文章浏览阅读430次。文件类boolean isHidden() (File Class boolean isHidden())This method is available in package java.io.File.isHidden(). 软件包java.io.File.isHidden()中提供了此方法。 This method is used to check whether the file is ..._android 隐藏文件ishidden 返回false

KinectV2的一些参数_kinect v2参数-程序员宅基地

文章浏览阅读4.8k次。1.硬件组成&参数彩色摄像机:19201080;30 or 15 FPS;多种图像格式可选(例如:RGBA–.png;YUV–MPEG压缩)2.红外投影机:主动投射近红外光谱,生成可被红外摄像机读取的激光散斑;512424;30 FPS;每像素16bit3.深度(红外)摄像机:测量范围:0.5 ~ 4.5 m;每像素16bit(该数据表示从深度摄像机到该物体的距离,单位:mm)*..._kinect v2参数

ipad和iphone适配_如何在iPhone,iPad和Mac上锁定Apple Notes-程序员宅基地

文章浏览阅读372次。ipad和iphone适配Khamosh Pathak Khamosh Pathak There are some things you’d rather not let anyone see including personal data or sensitive photos. The easiest way to protect them is by adding them to a loc..._mac note lock password not match

【李宏毅深度学习】阶段性小结_life-long/compression是什么-程序员宅基地

文章浏览阅读1.4k次。文章目录一、资源推荐二、菜鸡学习笔记三、小结四、下一阶段五、特别鸣谢一、资源推荐(1)Pytorch的vision库等:https://github.com/pytorch/vision等动手中出现问题时应多学习官方文档or维基百科(2)李宏毅机器学习课程 + 吴恩达深度学习(3)datawhale学习笔记二、菜鸡学习笔记(1)【李宏毅机器学习CP1-3】(task1)机器学习简介&分类|回归学习了上图的ML分类及应用,和如下的三个步骤及其细节:step1:模型假设,选择模型框架_life-long/compression是什么

随便推点

2020-10-28_数据库实体属性的划分复合属性-程序员宅基地

文章浏览阅读117次。多值属性、复合属性等概念 1).简单属性:不能再划分为更小部分的属性。 2).复合属性:可以再划分为更小的部分,也就是能再划分为一些其他属性的属性。 比如说:name属性可被设计为一个包括first_name,middle_name,lase_name的复合属性。 3).单值属性:数据库中,所定义的属性对于一个特定的实体都只有..._数据库实体属性的划分复合属性

Ext.Net 1.x_Ext.Net.GridPanel之右键菜单_ext.net contextmenuid-程序员宅基地

文章浏览阅读2.4k次。function deleteuser() { var record = ItemGrid.getSelectionModel().getSelected(); alert("删除物料:"+record.data.MB001.toString()); //Ext.net.DirectMethods.De_ext.net contextmenuid

ExtJS树型下拉框应用--地区选择-程序员宅基地

文章浏览阅读191次。1、效果如图 2、 引入TreeField控件(转载) Ext.form.TreeField = Ext.extend(Ext.form.TriggerField, { /** * @cfg {Boolean} readOnly * 设置为只读状态 * */ readOnly : ..._ext3 treefieldcfg

centos6.5编译安装zabbix2.4及微信企业号告警-程序员宅基地

文章浏览阅读84次。在centos6.5上编译安装zabbix2.4zabbix server安装节点为:192.168.1.36被监控主机节点为:192.168.1.37本来想在centos6.5上安装zabbix3.0,没想到装到第一步就进行不下去了,百度、谷歌好半天也没搜到答案,好多人也遇到同样的问题:就是进入zabbix的web页面,第一步点击下一步时,..._iptables 放行10051

C语言:输入密码,密码正确,提示“登录成功”,最多输入三次,超过次数跳出程序_c语言密码正确后跳出循环-程序员宅基地

文章浏览阅读1.5w次,点赞6次,收藏45次。#define _CRT_SECURE_NO_WARNINGS 1#include &lt;stdio.h&gt;#include &lt;string.h&gt;int main(){ int i = 0;//定义一个字符串,保存输入的密码 char password[] = { 0 }; //密码最多输入三次,三次结束,跳出此循环 for (i = 0; i &lt; ..._c语言密码正确后跳出循环

终端(Terminal)窗口的打开方式及常用终端命令_terminal终端怎么打开-程序员宅基地

文章浏览阅读10w+次,点赞47次,收藏238次。Terminal,是专门为程序员设计的,通过输入命令来操作电脑的一种方式 ,有些软件只提供了通过终端命令的方式来操作,如 node、git等。终端窗口有什么用?1. 常用的操作,比如创建文件夹、创建文件、移动文件、关机、锁屏等等,都可以使用终端窗口完成。2. 使用Git、Node、Vue等开发,必须要使用终端窗口。终端窗口有哪些:1. cmd 窗口--- 系统内置;2. powershell 窗口 --- 系统内置;3. Git --- 安装Git才有...如何打开终端窗口:W._terminal终端怎么打开

推荐文章

热门文章

相关标签