求延续子数组的最大和

求连续子数组的最大和

这个问题一般用动态规划算法可以再线性时间内得到解。

动态规划就是将大问题化为小问题，先把小问题解决了，最后大问题也就解决了。本问题是从一个元素开始，到两个元素，最后到数组的全部元素来逐步解决的

int main( void ) {timer t;//top_k_words();int a[]={1,2,3,-8,1,2,3,4,-99,100,101,-400,100,100,100,100,-100,900};vector<int> va(a,a+sizeof(a)/sizeof(int));print(va.begin(),va.end());int sum=va[0];int temp=va[0];for (vector<int>::size_type i=1;i<va.size();i++){temp=max(a[i],temp+a[i]);sum=max(temp,sum);}cout<<"max sub sum is : "<<sum<<endl;cout<<"time elapsed "<<t.elapsed()<<endl;return 0;}