目录
最大子序列的概念
具体求解算法
暴力算法
优化后的暴力算法
在线处理
分而治之
运行结果
-
最大子序列的概念
在计算机科学中,最大子数列问题的目标是在数列的一维方向找到一个连续的子数列,使该子数列的和最大。例如,对一个数列 −2, 1, −3, 4, −1, 2, 1, −5, 4,其连续子数列中和最大的是 4, −1, 2, 1, 其和为6。
-
具体求解算法
-
暴力算法
int max_sub_seq1(int *arr, int len) //初始版本 时间复杂度为O(n^3) { int cur_num; int max_num; if (!arr || len < 0) { printf("Error input arguements\n"); return -1; } int i, j ,k; for (i = 0; i < len; ++i) { for (j = i; j < len; j++) { cur_num = 0; for (k = i; k <= j; ++k) cur_num += arr[k]; if(cur_num > max_num) { max_num = cur_num; } } } return max_num; }
-
优化后的暴力算法
int max_sub_seq2(int *arr, int len) //稍加优化 时间复杂度为O(n^2) { int cur_num = 0; int max_num = 0; int i, j; if (!arr || len < 0) { printf("Error input arguements\n"); return -1; } for (i = 0; i < len; i++) { cur_num = 0; for (j = i; j < len; j++) { cur_num += arr[j]; if(cur_num > max_num) max_num = cur_num; } } return max_num; }
-
在线处理
备注:种方式只能用于一个数据元素非全负的数组序列,若数组序列为全负,则其子序列求和为)/*在线处理的思想来优化代码 时间复杂度为n,但是对于数据元素全为负数的序列求值为(0)会出错*/ int max_sub_seq3(int *arr, int len) { int i, j; int cur_num; int max_num; if (!arr || len < 0) { printf("Error input arguements\n"); return -1; } cur_num = max_num = 0; for (i = 0; i < len; i++) { cur_num += arr[i]; if(cur_num > max_num) max_num = cur_num; else if(cur_num < 0) { cur_num = 0; } } return max_num; }
-
分而治之
inline int max_three_num(int num1, int num2, int num3) //求得三数的最大值 { int max = 0; max = num1 > num2 ? num1:num2; max = num3 > max ? num3:max; return max; } int maxcross(int *arr, int left, int mid, int right) //求出有交叉的左右序列的和 { int i; int sum = 0; int leftSum = 0; int rightSum = 0; for (i = mid; i >=left; i--) { sum += arr[i]; if (sum > leftSum) leftSum = sum; } sum = 0; for (i = mid + 1; i <= right; i++) { sum += arr[i]; if (sum > rightSum) rightSum = sum; } return leftSum + rightSum; } int DivideandRule(int *arr, int left,int right) /* 分而治之*/ { int mid=0; int maxLeft=0, maxRight=0, maxMiddle=0; if (left == right) { if (arr[left] > 0) return arr[left]; else return 0; } mid = (left + right) / 2; maxLeft = DivideandRule(arr, left, mid); /*左序列递归求和*/ maxRight = DivideandRule(arr, mid + 1, right); /*右序列递归求和0*/ maxMiddle = maxcross(arr,left,mid,right); /* 有交集的左右序列求和 */ return max_three_num(maxLeft, maxRight, maxMiddle); }
-
运行结果