最大子列和问题

将一个问题的算法复杂度O(n^3)干道O(n^2)到O(nlog2n)到O(n)的过程是多么的feel at easy。

算法的魅力，解决同一大数量级问题的快与慢，明显体现，请撸码体验

测试源码：https://github.com/linrenyao/Algorithm/blob/master/MaxSumSubList.cpp

//穷举 O(n^3) int algorithm1(int list[],int n) { int MaxSum = 0,TempSum = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { TempSum = 0; for (int k = j; k < n; k++) { TempSum += list[k]; if (TempSum > MaxSum) MaxSum = TempSum; } } } return MaxSum; } //优化后的穷举，去除不必要的重复累加 O(n^2) int algorithm2(int list[], int n) { int MaxSum = 0, TempSum = 0; for (int i = 0; i < n; i++) { TempSum = 0; for (int j = i; j < n; j++) { TempSum += list[j]; if (TempSum > MaxSum) MaxSum = TempSum; } } return MaxSum; }

 

//分治算法(分儿治之，先分后治)   0(nlog2n) int algorithm3(int *list,int start,int end) { int mid = (end + start) / 2; int num = (end - start) / 2; if (num >= 1) { int leftMaxSubListSum, RightMaxSubListSum;        //递归左半部 leftMaxSubListSum = algorithm3(list, start, mid);        //递归右半部 RightMaxSubListSum = algorithm3(list, mid, end); //求左右两部分的最大子序列和 int MaxSubListSum = 0, TempSubListSum = 0; int i = 0; while (num--) { TempSubListSum += list[mid-1-i]; if (TempSubListSum > MaxSubListSum) MaxSubListSum = TempSubListSum; TempSubListSum += list[mid+i]; if (TempSubListSum > MaxSubListSum) MaxSubListSum = TempSubListSum; i++; }        //比较三个序列和 int maxSum = max(leftMaxSubListSum, RightMaxSubListSum) > MaxSubListSum ? max(leftMaxSubListSum, RightMaxSubListSum) : MaxSubListSum; return maxSum; } else{        //当序列中只有一个元素则返回，当前序列的唯一和，startindx 和endindx 差1 int MaxSubListSum = 0, TempSubListSum = 0; for (int i = start; i < end; i++) { TempSubListSum += list[i]; if (TempSubListSum > MaxSubListSum) MaxSubListSum = TempSubListSum; } return MaxSubListSum; } }

在线算法：选择当前相对解。 

//在线处理算法 O(n) int algorithm4(int list[], int n) { int MaxSum = 0, TempSum = 0; for (int i = 0; i < n; i++) { TempSum += list[i]; if (TempSum > MaxSum) MaxSum = TempSum; else if(TempSum < 0) TempSum = 0; } return MaxSum; }