博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
返回一个整数数组中最大子数组的和
阅读量:6591 次
发布时间:2019-06-24

本文共 989 字,大约阅读时间需要 3 分钟。

作业要求:

         1.程序必须能处理1000个元素;

         2.每个元素是int32类型的,出现子数组之和大于整型表示的最大范围会出现什么情况;

         3.输入一个整形数组,数组里面既有正数也有负数;

         4.数组中连续的一个或多个整数组成一个字数组,每个子数组都有一个和;

         5.求所有子数组的和的最大值,要求时间复杂度为O(n)。

设计思想:

#include "stdafx.h"

#include "time.h"

int _tmain(int argc, _TCHAR* argv[])

{

 return 0;

}

#include<iostream>

using namespace std;
int max(int a,int b)
{
if(a>b)
{
return a;
}
else
{
return b;
}
}
int maxsum(int a[], int n)
{
int i;
int maxsofar = 0;                                       
int maxendinghere = 0;                              
for (i = 0; i < n; i++)
{
maxendinghere = max(maxendinghere + a[i], 0);
maxsofar = max(maxsofar, maxendinghere);
}
return maxsofar;
}
int main()
{
int n, i=0;
cout<<"请输入个数:";
cin>>n;

int a[1000]={0};

srand(time(NULL));
for(i=0;i<n;i++)
{
a[i]=rand()%2000-1000;
}

cout<<"生成的数组";

for(i=0;i<n;i++)
{
cout<<a[i]<<"\t";
}
int max=maxsum(a, n);
cout << "最大子数组的和为:" << max << endl;

system("pause");

return 0;
}

运行结果:

 

伙伴:高尉雅

 

总结:之前的程序知识忘得差不多了,然后通过和同学一起讨论学习后,想起来一些知识。通过这次学习又让我复习了一下以前的知识。并且认识到自己还有许多不足,以后还需多多努力。

 

 

转载于:https://www.cnblogs.com/wushao12345/p/9787170.html

你可能感兴趣的文章
最终的解决方案感到担心初中——现在,你可以移动
查看>>
jquery选择器(原创)<四>
查看>>
使用Eclipse+Maven+Jetty构建Java Web开发环境(几个教程综合集成2014发行)
查看>>
位运算
查看>>
微信公众号-增加智能自动回复的功能--使用图灵机器人
查看>>
pip 直接安装tar.gz zip文件包 (windows linux mac 可用)
查看>>
名单(两)——基本操作单向链表(创、删、印、节点统计数)
查看>>
Swift - 使用MapKit显示地图,并在地图上做标记
查看>>
图像局部特征点检测算法综述【修正排版】
查看>>
UART中的硬件流控RTS与CTS【转】
查看>>
Linux 火狐浏览器安装Flash插入
查看>>
面向对象编程案例03---继承之高级部分
查看>>
LeetCode——Gas Station
查看>>
Redhat 用代理连外网
查看>>
git-push(1) Manual Page
查看>>
【蓝桥杯】 PREV-1 核桃数
查看>>
东北四省杯经验
查看>>
GIS开发离线地图应用-初识gis
查看>>
java日期工具类DateUtil
查看>>
SharePoint 2013 error The given assembly name or codebase System.ServiceModel.dll was invalid
查看>>