大三时候，面试微软的实习生，电话面试了我一个多小时，果然名不虚传，除了最开始简单的自我介绍和项目介绍外，大部分时间是徒手写代码，在远程屏幕编辑器上写代码。 面试官很nice，讲话方面完全没有什么架子，可以说很温柔了哈哈哈哈（男的）。一共三道题，第一道是删除链表的倒数第k个节点：用两个指针，第一个延缓第二个k步遍历链表，第二个到了底，那么第一个指针指的就是倒数第k个了。第二道题是求不重复的最大子串长度：读字符串数据，存到队列里，每新读入一个，扫描一遍已读入的表，有重复则出队直到该重复的字符出队，一直记录队列的最大长度。最终的最大长度就为最大子串长度。第三道题就是如题了，给我十来分钟，我没想到比O（N^2）小的时间复杂度。特此记录！
#include "stdafx.h" #include <iostream> using namespace std; /****环境：VS2015*********/ /************************* 函数：求最大子列和1 输入：数组a，数组长度 N 输出：最大子列和 时间复杂度：O(N^3) *************************/ int maxSubSeqSum1(int N, int a[]) { int ThisSum, MaxSum = 0; for (int i = 0;i < N;i++) { for (int j = i;j < N;j++) { ThisSum = 0; for (int k = i;k < j;k++) ThisSum += a[k]; if (ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum; } /************************* 函数：求最大子列和2 输入：数组a，数组长度 N 输出：最大子列和 时间复杂度：O(N^2) *************************/ int maxSubSeqSum2(int N, int a[]) { int ThisSum, MaxSum = 0; for (int i = 0;i < N;i++) { ThisSum = 0; for (int j = i;j < N;j++) { ThisSum += a[j]; if (ThisSum > MaxSum) MaxSum = ThisSum; } } return MaxSum; } /************************* 函数：求最大子列和3(分而治之递归) 输入：数组a，数组长度 N 输出：最大子列和 时间复杂度：O(NlogN) *************************/ int maxSubSeqSum3(int h, int a[],int t) { int ThisSum = 0, MaxSum = 0, MaxLeft = 0, MaxRight = 0, MaxContainBorderLeft = 0, MaxContainBorderRight = 0, MaxContainBorder=0; if ((t - h) / 2 > 0) { MaxLeft = maxSubSeqSum3(0, a, (t - h) / 2); //求两个子列的最大子列和 MaxRight = maxSubSeqSum3((t - h) / 2, a, (t - h)); } //求跨越边界的最大子列和 for (int i = (t - h) / 2;i > 0;i--) { ThisSum += a[i]; if (MaxContainBorderLeft < ThisSum) MaxContainBorderLeft = ThisSum; } ThisSum = 0; for (int i = (t - h) / 2+1;i < t-h;i++) { ThisSum += a[i]; if (MaxContainBorderRight < ThisSum) MaxContainBorderRight = ThisSum; } MaxContainBorder = MaxContainBorderLeft + MaxContainBorderRight; //求三个子列和中最大的 if (MaxLeft > MaxRight) MaxSum = MaxLeft; else MaxSum = MaxRight; if (MaxSum < MaxContainBorder) MaxSum = MaxContainBorder; return MaxSum; } /************************* 函数：求最大子列和4(在线处理) 输入：数组a，数组长度 N 输出：最大子列和 时间复杂度：O(N) *************************/ int maxSubSeqSum4(int N, int a[]) { int ThisSum=0, MaxSum = 0; for (int i = 0;i < N;i++) { ThisSum+=a[i]; if (ThisSum > MaxSum) MaxSum = ThisSum; else if (ThisSum < 0)//如果当前子列和为负数 ThisSum = 0;//则最大子列和不可能包含上述子列，弃之 //（既然是突然变小，则最后的那个数是使其变负的数，要想用前面的值，则必须使用这个负数） } return MaxSum; } /***********测试***********/ int main() { int x[14] = { -1,5,3,-9,4,-2,4,7,-3 ,-4,7,-3,10}; cout << maxSubSeqSum1(14, x)<<endl; cout << maxSubSeqSum2(14, x) << endl; cout << maxSubSeqSum3(0, x, 13) << endl; cout << maxSubSeqSum4(14, x) << endl; system("pause"); return 0; }欢迎留言反驳提问，谢谢。
