如何求连续几个数之和的最大值

给定一组数，有正有负，求连续的几个数之和的最大值？并求出是从第几个数开始，第几个数结束？如果有多个序列可组成相同的最大值，则选取最开始的一个序列。（注：这两天看《编程之美》，发现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]中连续数之和最大的部分（如果最大部分存在相等，则优先找最短的）。
这道题和上面的题类似，只不过本人还是想不出怎么取最短，只做到取首次取得最大值。

赞 (0)

相关推荐

  • 如何求连续几个数之和的最大值

    给定一组数,有正有负,求连续的几个数之和的最大值?并求出是从第几个数开始,第几个数结束?如果有多个序列可组成相同的最大值,则选取最开始的一个序列.(注:这两天看<编程之美>,发现2.14节,求数组的子数组之和的最大值,跟这个题十分相似,但是没有要求求出开始喝结束的位置,只要求求出最大值,解题思路跟下面的代码相似,但只用了两个变量,没有用数组,做到时间复杂度O(n),空间复杂度O(1))用程序设计实现.我实现了一种方法,跟大家分享一下,如果朋友你有更好的方法来解决这个问题,希望你能回复,与大家分

  • 求最大子数组之和的方法解析（2种可选）

    问题描述:一个有n个元素的数组,这n个元素可以是正数也可以是负数,求最大子数组的和. 方法1:蛮力法 思路:最简单也是最容易想到的方法就是找出所有子数组,然后求所有子数组的和,在所有子数组的和中取最大值. /** * 方法1(蛮力法):两次循环求最大子数组之和 */ public static int maxSubArray1(int[] a){ int i,j; int ThisSum=0; int MaxSum=0; for (i = 0; i < a.length; i++) { This

  • PHP实现求连续子数组最大和问题2种解决方法

    本文实例讲述了PHP实现求连续子数组最大和问题2种解决方法.分享给大家供大家参考,具体如下: 问题描述 求子数组的最大和 题目描述: 输入一个整形数组,数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和. 求所有子数组的和的最大值.要求时间复杂度为O(n). 关于连续子数组最大和这个问题,有两种解法,一种是动态规划 解法如下: function getMaxSubSum($arr){ $curSum = $arr[0]; $maxSum = $arr[0];

  • python+numpy按行求一个二维数组的最大值方法

    问题描述: 给定一个二维数组,求每一行的最大值 返回一个列向量 如: 给定数组[1,2,3:4,5,3] 返回[3:5] import numpy as np x = np.array([[1,2,3],[4,5,3]]) # 先求每行最大值得下标 index_max = np.argmax(x, axis=1)# 其中,axis=1表示按行计算 print(index_max.shape) max = x[range(x.shape[0]), index_max] print(max) # 注

  • C语言求连续最大子数组和的方法

    本文实例讲述了C语言求连续最大子数组和的方法,是非常实用的技巧.分享给大家供大家参考. 具体实现方法如下: #include <iostream> using namespace std; int array[] = {1, -2, 3, 10, -4, 7, 2, -5}; //int array[] = {-10, -1, -2, -3, -4, -5}; const int size = sizeof array / sizeof *array; int maxSubArray(int

  • C++实现二分法求连续一元函数根

    本文实例为大家分享了C++实现二分法求连续一元函数根的具体代码,供大家参考,具体内容如下 设计一个用二分法求连续一元函数根的通用函数solve 此函数有三个参数: 第一个是函数指针,指向所要求根的连续函数 第二.三个参数指出根的区间,且确保函数在区间的两个端点异号 函数的返回值为求得的解 要求编写main函数如下: double fun(double x) { double y; y=4*pow(x,3)-6*pow(x,2)+3*x-2; return y; } int main() { co

  • golang求连续子数组的最大和实例

    golang求连续子数组的最大和实例

    问题描述: 给定一个数组 array[1, 4, -5, 9, 8, 3, -6],在这个数字中有多个子数组,子数组和最大的应该是:[9, 8, 3],输出20,再比如数组为[1, -2, 3, 10, -4, 7, 2, -5],和最大的子数组为[3, 10, -4, 7, 2],输出18. 代码如下: package main import ( "fmt" ) func getMaxSum(arr []int) int { var sum, maxSum int for i :=

  • 把1316这个数表示成两个数的和，其中一个为13的倍数，另一个是11的倍数，求这两个数。

    算法分析: 1316,显然1300是13的倍数,但16不是11的倍数,可以想到从1300上任意减去N个13的倍数其结果仍然是13的倍数,那么只要16加上这个减去的N个13的倍数其和是11的倍数,这两个数就解出来了,答案可能不只一个,但是我们只求一对解就可以了. 仔细观察不难发现:(16+13*3)+(1300-13*3)=1316,但是我们需要用代码实现: 复制代码 代码如下: <?php $n=1316; $i=0;//减去的第N个13,进行初始化为0 $y=16+13*$i;//1316分出

  • Python贪心算法实例小结

    本文实例讲述了Python贪心算法.分享给大家供大家参考,具体如下: 1. 找零钱问题:假设只有 1 分. 2 分.五分. 1 角.二角. 五角. 1元的硬币.在超市结账 时,如果 需要找零钱, 收银员希望将最少的硬币数找给顾客.那么,给定 需要找的零钱数目,如何求得最少的硬币数呢? # -*- coding:utf-8 -*- def main(): d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存储每种硬币面值 d_num = [] # 存储每种硬币的数量 s

  • 浅谈单调队列、单调栈

    初谈这个话题,相信许多人会有一种似有所悟,但又不敢确定的感觉.没错,这正是因为其中"单调"一词的存在,所谓单调是什么,学过函数的people都知道单调函数或者函数的单调性,直白一点说单调就是一直增或一直减.例如:1,3,5,9就是一个单调增数列,数列中不存在后一个数比前一个数小的现象.那么同样,在这里谈到的话题也有类似特点. 先说一下单调队列吧!      单调队列,就是一个符合单调性质的队列,它同时具有单调的性质以及队列的性质.他在编程中使用频率不高,但却占有至关重要的地位.它的作用

随机推荐