【微软面试题】找出任何相邻子向量的最大和

输入一个具有个整数的向量x，输出任何子向量相加的最大和。
如输入：int a[] = {31,-41,59,26,-53,58,97,-93,-23,84};
则输出：187

/** 找出任何相邻子向量的最大和* xtfggef 2012/5/7*/#include<stdio.h>int max(int a,int b){return (a>b)?a:b;}void main(){int a[10] = {31,-41,59,26,-53,58,97,-93,-23,84};int maxsofar = 0;int maxendinghere = 0;for(int i=0; i<10; i++){//遇到负数，直接赋0，相当于跳过//遇到大一点的数，从该数开始maxendinghere=max(maxendinghere+a[i],0);maxsofar=max(maxsofar,maxendinghere);}printf("%d\n",maxsofar);}

仔细研究了下，好精妙的算法啊！建议读者走一遍程序，观察变化，体会细节！