如何求連續(xù)幾個(gè)數(shù)之和的最大值

更新時(shí)間：2013年05月28日 17:34:56 作者：

本篇文章是對(duì)如何求連續(xù)幾個(gè)數(shù)之和的最大值進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

給定一組數(shù)，有正有負(fù)，求連續(xù)的幾個(gè)數(shù)之和的最大值？并求出是從第幾個(gè)數(shù)開始，第幾個(gè)數(shù)結(jié)束？如果有多個(gè)序列可組成相同的最大值，則選取最開始的一個(gè)序列。（注：這兩天看《編程之美》，發(fā)現(xiàn)2.14節(jié)，求數(shù)組的子數(shù)組之和的最大值，跟這個(gè)題十分相似，但是沒有要求求出開始喝結(jié)束的位置，只要求求出最大值，解題思路跟下面的代碼相似，但只用了兩個(gè)變量，沒有用數(shù)組，做到時(shí)間復(fù)雜度O（n），空間復(fù)雜度O（1））
用程序設(shè)計(jì)實(shí)現(xiàn)。我實(shí)現(xiàn)了一種方法，跟大家分享一下，如果朋友你有更好的方法來(lái)解決這個(gè)問(wèn)題，希望你能回復(fù)，與大家分享一下。
另外，如果題目改成：“給定一組數(shù)，有正有負(fù)，求連續(xù)的幾個(gè)數(shù)之和的最大值？并求出是從第幾個(gè)數(shù)開始，第幾個(gè)數(shù)結(jié)束？如果有多個(gè)序列可組成相同的最大值，則選取序列中數(shù)字最少的那個(gè)。”該怎么寫程序，本人思考良久沒有想到好的辦法。求指點(diǎn)?。。。。。?！
下面是我實(shí)現(xiàn)的C++代碼：

復(fù)制代碼代碼如下:

#include "stdafx.h"
#include <iostream>
using namespace std;
int GetMaxs(int arrary[],const int n)
{ 
 int max = 0, temp = 0;  //max最大值，temp臨時(shí)變量
 int begin = 0, end = 0;
 int *maxlist= new int[n]; //maxlist[n],一個(gè)數(shù)組，跟原數(shù)組一般大
 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]; //更新最大值數(shù)組
  }
  else
  {
   maxlist[i] = arrary[i]; //更新最大值數(shù)組
  }
  if (maxlist[i] > max)
  {
   max = maxlist[i]; //用當(dāng)前值更新最大值
   end = i; //設(shè)置終點(diǎn)索引
  }
 }
 //下面幾句是尋找起始點(diǎn)
 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;
}

另外一道很相似的題目：有一個(gè)數(shù)組a[n]，里面的數(shù)只有兩種：-1和1。 i、j是兩個(gè)整數(shù)，假設(shè)0 <= i < j <= n -1 ,找出a[i]到a[j]中連續(xù)數(shù)之和最大的部分（如果最大部分存在相等，則優(yōu)先找最短的）。
這道題和上面的題類似，只不過(guò)本人還是想不出怎么取最短，只做到取首次取得最大值。

您可能感興趣的文章: