自己先后分别在《编程之美——微软面试心得》和《编程珠玑》中看到了这样的一个经典的例子:在线性时间内求向量的任何连续子向量中的最大和。
本来是O(n3)的算法,经过一步步的改进后,最终得到了O(n)的算法,这个思维的过程实在是令人叹服。这看完后个例子后,试问了下自己,如果在没有任何提示的前提下,让自己想出这个方法几乎是不可能的,而现在我知道了这个方法,怎么才能让它真正属于自己呢?
我想到的是拓展!!
在这两本书中都只是给出了求得最大和的算法,而没有得出具体是哪一段有这个最大和。
经过两个小时的思考后(包括上机调试时间),得出了下面这个可以同时求得区间的C++代码。
#include "stdafx.h"#include <vector>#include <iostream>usingnamespace std;int _tmain(int argc, _TCHAR* argv[]){ staticconstint N =5; //int v[N] = {31, -11, 59, /*26, -53, 58, 97, -93, -23, 84*/};int v[N] = {1,-2,3,-1,5}; vector<int> arr(v,v+N) ; int maxhere=0; int maxSum=0; //最终的结果保留在a2,b2中,a1,b1只是个临时变量int a1=0, b1=0, a2=0, b2=0; //设定一个标志,是否重置a1bool isFirst=true; for (int i=0;i<arr.size();++i) { if(maxhere+arr[i] >0) { maxhere+=arr[i]; if (isFirst) { a1=i; } isFirst =false; b1=i; } else { //当和小于0时就要重置a1,b1 isFirst =true; maxhere =0; a1=i; b1=i; } if(maxSum < maxhere) { maxSum = maxhere; a2=a1; b2=b1; } } cout << a2 <<":"<<b2<<endl; cout << maxSum <<endl; system("pause"); return0;}
得出了上面的代码后,自己也更加深刻地了解了这个算法的精髓。这个算法很经典,本人就不给出每一步的说明了,有兴趣的朋友可以用这个代码进行单步调试来了解。如果理解书上的原始代码,看懂这个代码就没有任何困难了。
原文链接: https://www.cnblogs.com/xiangism/archive/2010/04/30/1724882.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/10522
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!