面试归来，有一个笔试题挺有意思，现奉上题目和我的答案，兄弟们给评评看

Question

数据结构与算法分析
C语言描述 21页
int maxsub(const int a[],int n)
{
int  thissum=0,maxsum=0,j=0;
for(j=0;j<n;++j){
thissum += a[j];
if(thissum>maxsum)
maxsum=thissum;
else if(thissum <0 )
thissum =0;
}
return maxsum;
}

Answer 1

假设a[i]到a[k]即为要求的连续段，那么从a[0]～a[i]、a[k]~a[n-1]的和肯定不为正小弟愚昧 请问为什么一定不为正

Answer 2

我写了一个算法测试了一下,复杂度为0(n*n).int CountMaxContinueValue(const int* pArray,int nSize)
{ int nIndexLeft;
int nIndexRight; int nMaxValue = 0;
int nSaveLeft = 0;
int nSaveRight = 0; nIndexLeft = 0; while (nIndexLeft < nSize-1)
{
if (pArray[nIndexLeft] <= 0)
{
nIndexLeft = nIndexLeft+1;
continue;
} nIndexRight = nIndexLeft +1; int nTempValue = pArray[nIndexLeft]; while (nIndexRight < nSize)
{
nTempValue += pArray[nIndexRight];

if (nTempValue > nMaxValue)
{
nMaxValue = nTempValue;
nSaveLeft = nIndexLeft;
nSaveRight = nIndexRight;
} nIndexRight += 1;
} nIndexLeft += 1; } cout<<"the max value is "<<nMaxValue<<endl;
cout<<"left from "<<nSaveLeft<<endl;
cout<<"right end "<<nSaveRight<<endl; return nMaxValue;
}

Answer 3

没有楼主想的那么复杂：
#include <iostream>
#include <cmath>
#include <ctime>using namespace std;int main() {
        const int length = 20;
        int data[length];
        int max = 0;
        
        srand(time(0));
        for (int i = 0; i < length; i++) {
                data[i] = rand() % 20 - 5;
                cout << data[i] << "\t";
        }
        
        cout << endl;
        max = data[0];
        for (int i = 0; i < length; i++) {
                int temp_max = data[i];
                for (int j = i+1; j < length; j++) {     
                        if ((temp_max + data[j]) >= temp_max) {
                                temp_max += data[j];
                        } else {                            
                                break;
                        }
                }
                if (temp_max > max) {
                        max = temp_max;
                }
        }
        
        cout << "The max continuous max value is " << max << endl;
}

Answer 4

是这个意思吧:+------+------+-----+------+-----+------+-----+--------+
| a[0] | a[1] | ... | a[i] | ... | a[j] | ... | a[N-1] |
+------+------+-----+------+-----+------+-----+--------+
                        |____________|
                               |
                              SUM(j-i+1)当a一定,N一定,M一定时(M<=N)求这个SUM(M)的最大值那么就从a[0]+...+a[M-1]算到a[N-M]+...+a[N-1]取最大值不就是嘛?

Answer 5

是这个意思吧:+------+------+-----+------+-----+------+-----+--------+
| a[0] | a[1] | ... | a[i] | ... | a[j] | ... | a[N-1] |
+------+------+-----+------+-----+------+-----+--------+
                        |____________|
                               |
                              SUM(j-i+1)

Answer 6

Max=0,temp1=0,temp2=0;
for(int i;i<n;i++)
{
   Sum=a[i];
   temp1=i;//记录位置
   Max=Sum;
   for(int j=i+1;j<n;i++)
   {
      Sum+=a[j];
      if(Sum>Max)
      {
         Max=Sum;
         temp2=j;//记录位置
       }
   } 
}
楼下们说说看吧,我也不太清楚!

Answer 7

int max_sum = 0xFFFFFFFF;
int sum = 0;
for(int j = 0; j < n;j ++){
 sum = 0;
 for(int k = n - 1; k >= j; k--){
    sum += a[k];
 }
 if(sum > max_sum){
    max_sum = sum;
  }
 }
}

Answer 8

这个题我见过的，是有标准算法的，好象有一年浙大的考研试题上有的，具体怎么做，我不会，反正当时我同学问了一个专门参加ACM的，说很简单的，算法复杂度nlog2n吧

Answer 9

假设a[i]到a[k]即为要求的连续段，那么从a[0]～a[i]、a[k]~a[n-1]的和肯定不为正。
-----------------------
怎么解释下面的数列：
1,2,3,-1,6,7,8,-1,9
a[4]到a[6]为要求的连续段，a[0]～a[4]、a[6]~a[8]的和???int sum = 0,sumo = 0;
int j=0,jc=0,k=0;
for(int i=0;i<n;i++)
{
   if(a[i] < 0)
   {
    if(sumo > sum)
    {
    sum = sumo;
    j = jc;
    k = i - 1;
    }
   
    i++;
    while(a[i] < 0)
    i++;
   
    sumo = 0;   
    jc = i;
   }
   sumo += a[i];
}
if(sumo > sum)
{
sum = sumo;
j = jc;
k = n - 1;
}
j,k,sum就是最终值

Answer 10

按照楼上的例子1,2,3,-1,6,7,8,-1,9
结果应该是0～8楼主说的没错，“假设a[i]到a[k]即为要求的连续段，那么从a[0]～a[i]、a[k]~a[n-1]的和肯定不为正。”如果为正的话，那结果就应该是整个数组。

Answer 11

数组A[0...n],连续段为k个，最大值为dbMax;如果k > n无解
dbMax = 0;
for(int i = 0; i < n && i < k; k ++)
   dbMax += A[i];
for(i = k; i < n; i ++)
  dbMax = dbMax + A[i] > dbMax ? dbMax + A[i] : dbMax;

Answer 12

leosheng, 全为负数也可以，不过全为负数的话，这个最大加和就一定是负值最小的那个一个数（因为左右加都会使它变小）。不过这个算法一样好用，只不过见一个扔一个就是了。

Answer 13

// 123max.cpp : Defines the entry point for the console application.
//#include "stdafx.h"const int N = 10;
const int LEN = 5;int main(int argc, char* argv[])
{
int arr[N]={0};
int sum = 0;
int sumtmp = 0;
int ban = 0; //差'额 int i =0; for (i=0; i<N; i++)
{
arr[i] = i*6-i*i;
} for (i=0; i<LEN; i++)
{
sum += arr[i];
} for (i=LEN; i<N; i++)
{
ban = arr[i] - arr[i-LEN];
if(ban >0)
{
sumtmp = sum;
sum += ban;
}
} for (i=0; i<N; i++)
{
printf("%d\t",arr[i]);
}
printf("\n\nsum=\t%d\n",sum); return 0;
}就这样而已吧