Question

高分，请问下面的C/C++编程题有什么比较有效率的解决方法？

我是一个编程菜鸟，遇到一道题，题目大致上是这个意思的，一组数字，存在一个数组里面，然后搜索这个数组中的固定长度的一段，让这一段是段内这些数的总和最大的，输出这个最大的和。

除了穷举法（即求出所有的可能的和，并输出最大的值）之外，有没有什么更有效率的算法，各位高手只需要给我个想法就可以了，就一个方案，谢谢。

Answer 1

固定一段？意思是连续的喽？

思路：
如果数据是连续的话，就不用每次都求和。
因为下一段数据的和 = 刚才求出的和 - 第一个旧元素值 + 后面新加的元素值。
中间段的元素就不需要再重新求和了。这样就可以省去大量的求和时间。

定义两个指针分别指向最开始这一段的一头和一尾，然后求和。
再定义两个指针，用于存放己找到最大段的地址。

然后扫描：
尾指针++，新段的和 + 尾值 - 首值，首指针 ++。

例：
long int GetClipMax(int *Buffer, int size, int clipCount){
// Buffer 为需要扫描的数组。
// size 为数组 Buffer 的长度。
// clipCount 为固定段的长度。
long sum=0; // sum 用于存放扫描到的段内数字和总和。
long max_sum = 0; // max_sum 用于存放目前扫描到的最大和。
for (int t = 0;t<clipCount;t++) // 先把第一段的和求出。
sum += Buffer[t];
max_sum = sum; // max_sum 是用来存放己描到的最大和，但是目前只描到第一组，所以只好暂时把第一段的和作为最大和。

// 然后，开始扫描。
int * pFront = Buffer; // pFront 是指针，用来指向段的第一个元素。
int * pBottom = pFront + clipCount - 1; // pBottom 也是指针，用来指向段的最后一个元素。‘+ clipCount - 1’代表向后移几个元素。
/*
例，要指向 Buffer 的第五个元，但是 Buffer 己经是第一个元素，要指第五个元素要向后移4位，所以用：
Buffer + 5 - 1， 或者 Buffer + 4
*/

while(pBottom - Buffer < size){ // While 循环就不用我说明了吧，自己看书。
// pBottom - Buffer ，两个同类型指针相减，可以求出这两个指针所指的元素位置上相差几个元素的置位。
// 如果 相差的元素的位置 大于 size （Buffer 的长度）就说明，pBottom 己经把 Buffer 都指完了。扫描就可以结束了。
pBottom++; // pBotom 向后移一个元素。
sum = sum - *pFront + *pBottom;
/* 因为指针 pBottom 己经向后移了一个元素。
所以，pBottom 指的是后面加进来的新元素，
pFront 还没有移，所以指的是旧段的第一个元素。所以要从 sum 中减掉。
*/
pFront ++; // 然后再来把 pFront 向后移一个元素的位置。

(sum > max_sum ? max_sum = sum : 0 ); //如果刚算出来的 sum 比 max_sum 大，则要记录最大的 sum 值。
// 这样，就完成了一扫描的一步。

}

return max_sum; //最后，把算出来的最大值返回。
}

整个代码可以简写为：

long int GetClipMax(int *Buffer,int size,int clipCount){
long int sum = 0, max_sum = 0;
int *pFront=Buffer,*pBottom=pFront+clipCount-1;

for(int t=0;t<clipCount;t++)sum+=Buffer[t];
max_sum = sum;

while(pBottom-Buffer<size){
sum += ( *(++pButtom) - *(pFront++));
(sum>max_sum?max_sum=sum;0);
}
return max_sum;
}

再不明白，就去翻翻书吧。
祝楼主顺利。

Answer 2

其实穷举法就不错啊，计算机本来就很笨，你让他使用那个方法也花不了什么时间啊

Answer 3

还是 穷举法，不过 计算和的算法可以稍微优化一下，不必段内的每一个元素都相加一遍。
比如数组 a={1，5,77,1,2,664,5,6,77,8，98,9，}
假设给的固定长度是len= 5，那么第一次，从数组下标0开始到4，不得不每一个都加一遍，计算出第一段的总和 sum_max=86；并记住此时段落的和 sum_current=86;
从数组第二个元素开始i=1，计算第二个段落的和 就不需要全部加起来了，注意一下第一段和第二段只有 两个元素不同，所以，第二段的和sum 等于 sum0-a[i-1]+a[len+(i-1)]=749，然后把这个和跟第一段的sum_max比较，将较大的和 赋给sum_max,同时更新sum_current=第二段的和(749);如此直到最后一个段落。
总的思想是减少每段的加减法次数，这样当计算大量数据的时候就很有优势了

Answer 4

我归纳的，可以参考下！过程比较漫长，得一步一个脚印
VC之路

一：第一阶段
C语言-------《C语言设计》 作者：谭浩强
二：第二阶段
C++ Primer, 4rd Edition

（入门类：
C++ Primer, 4rd Edition
Thinking in C++, 2nd Edition
The C++ Standard Library: A Tutorial and Reference

进阶类：
The C++ Programming Language, Special Edition
The Design and Evolution of C++
Inside C++ Object Model
C++ Templates: The Complete Guide
STL 源码剖析
Generic Programming and the STL
Modern C++ Design: Generic Programming and Design Patterns Applied
应用技巧类：
Effective C++, 2nd Editon
More Effective C++
Exceptional C++
More Exceptional C++
Effective STL
Ruminations on C++）
三：第三阶段
API/SDK------------- 《windows程序设计》（Jeff Prosise）
四:第四阶段
MFC----《VC++技术内幕》、《深入浅出MFC》
及视频教程孙鑫 VC++6.0
五：第五阶段
COM/DCOM/ATL/COM+---------《COM技术内幕》
1. 注：前提具备了一定的数学,数据结构及算法,操作系统等基础知识，学好C++是很关键的，尤其要理解清楚OOP思想。