手机
当前位置:查字典教程网 >编程开发 >C语言 >如何求连续几个数之和的最大值
如何求连续几个数之和的最大值
摘要:给定一组数,有正有负,求连续的几个数之和的最大值?并求出是从第几个数开始,第几个数结束?如果有多个序列可组成相同的最大值,则选取最开始的一个...

给定一组数,有正有负,求连续的几个数之和的最大值?并求出是从第几个数开始,第几个数结束?如果有多个序列可组成相同的最大值,则选取最开始的一个序列。(注:这两天看《编程之美》,发现2.14节,求数组的子数组之和的最大值,跟这个题十分相似,但是没有要求求出开始喝结束的位置,只要求求出最大值,解题思路跟下面的代码相似,但只用了两个变量,没有用数组,做到时间复杂度O(n),空间复杂度O(1))

用程序设计实现。我实现了一种方法,跟大家分享一下,如果朋友你有更好的方法来解决这个问题,希望你能回复,与大家分享一下。

另外,如果题目改成:“给定一组数,有正有负,求连续的几个数之和的最大值?并求出是从第几个数开始,第几个数结束?如果有多个序列可组成相同的最大值,则选取序列中数字最少的那个。”该怎么写程序,本人思考良久没有想到好的办法。求指点!!!!!!!

下面是我实现的C++代码:

复制代码 代码如下:

#include "stdafx.h"

#include <iostream>

using namespace std;

int GetMaxs(int arrary[],const int n)

{

int max = 0, temp = 0; //max最大值,temp临时变量

int begin = 0, end = 0;

int *maxlist= new int[n]; //maxlist[n],一个数组,跟原数组一般大

max = maxlist[0] = arrary[0];

begin = end = arrary[0];

for (int i = 1; i < n; i++)

{

temp = maxlist[i - 1] + arrary[i];

if (temp > arrary[i])

{

maxlist[i] = maxlist[i - 1] + arrary[i]; //更新最大值数组

}

else

{

maxlist[i] = arrary[i]; //更新最大值数组

}

if (maxlist[i] > max)

{

max = maxlist[i]; //用当前值更新最大值

end = i; //设置终点索引

}

}

//下面几句是寻找起始点

int j = end, sum = 0;

while (j < n && sum != max )

{

sum += arrary[j];

j --;

}

begin = ++j;

cout << "The max sum is: " << max << endl;

cout << "The begin position is: " << ++begin << endl;

cout << "The end position is: " << ++end << endl;

return 0;

}

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

{

//int a[] = {-1,-1,-1,1,1,1,-1,-1,-1,-1,1,1,-1,1,1,-1};

int a[] = {5,8,12,-25,-15,56,-14,25,2,-10,6};

int n = sizeof(a)/sizeof(a[0]);

GetMaxs(a,n);

return 0;

}

另外一道很相似的题目:有一个数组a[n],里面的数只有两种:-1和1。 i、j是两个整数,假设0 <= i < j <= n -1 ,找出a[i]到a[j]中连续数之和最大的部分(如果最大部分存在相等,则优先找最短的)。

这道题和上面的题类似,只不过本人还是想不出怎么取最短,只做到取首次取得最大值。

【如何求连续几个数之和的最大值】相关文章:

解析C#中不一样的大小写转换

使用C# 判断给定大数是否为质数的详解

浅谈内联函数与宏定义的区别详解

字符串拷贝函数memcpy和strncpy以及snprintf 的性能比较

关于C++中的友元函数的一些总结

引用参数和传值参数的区别深入解析

C++函数重载的深入解析

基于C中一个行压缩图的简单实现代码

c++实现strcat字符串连接库函数的方法详解

数组和指针的区别深入剖析

精品推荐
分类导航