最大子数组问题
定义
给定整数A1, A2, …, An(其中可能是负数)，求k的最大值和序列的起始位置（为了方便起见，如果所有整数均为负数，则最大子序列和为0），使用四种算法（根据运行时间区分）解决这个问题。
运行时间为θ(n3)
使用了三个for循环，在最坏情况下，运行时间为θ(n3)
C语言实现代码
#include<stdio.h> #define LEN(array) (sizeof(array)/sizeof(array[0])) void maxsubarray(int *array, int len, int *, int *); main(){ int array[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}; int i, start, end; printf("原始数组:\n"); for (i = 0; i < LEN(array); i++) printf("%5d", array[i]); putchar('\n'); maxsubarray(array, LEN(array), &start, &end); printf("最大子序列的起始位置为：%d, 终止位置为：%d\n", start+1, end+1); printf("最大子序列为: "); for (i = start; i <= end; i++) printf("%5d", array[i]); putchar('\n'); putchar('\n'); } void maxsubarray(int *array, int len, int *start, int *end){ int i, j, k, sum, maxsum; maxsum = 0; for (i = 0; i < len; i++){ for (j = i; j < len; j++){ sum = 0; for (k = i; k <= j; k++){ sum += array[k]; if (sum > maxsum){ maxsum = sum; *start = i; *end = j; } } } } printf("\n子序列的求和最大值为： %d\n", maxsum); }
运行时间为θ(n2)
使用了两个for循环，最坏情况下运行时间为θ(n2)
C语言实现代码
#include<stdio.h> #define LEN(array) (sizeof(array)/sizeof(array[0])) void maxsubarray(int *array, int len, int *, int *); main(){ int array[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}; int i, start, end; printf("原始数组:\n"); for (i = 0; i < LEN(array); i++) printf("%5d", array[i]); putchar('\n'); maxsubarray(array, LEN(array), &start, &end); printf("最大子序列的起始位置为：%d, 终止位置为：%d\n", start+1, end+1); printf("最大子序列为: "); for (i = start; i <= end; i++) printf("%5d", array[i]); putchar('\n'); putchar('\n'); } void maxsubarray(int *array, int len, int *start, int *end){ int i, j, sum, maxsum; maxsum = 0; for (i = 0; i < len; i++){ sum = 0; for (j = i; j < len; j++){ sum += array[j]; if (sum > maxsum){ maxsum = sum; *start = i; *end = j; } } } printf("\n子序列的求和最大值为： %d\n", maxsum); }
运行时间为θ(nlgn)
使用分治法求解：
假设我们要寻找子数组A[low..high]的最大子数组，使用分治技术意味着要将子数组划分为两个规模尽量相等的子数组，也就是说，要找到子数组的*位置mid，然后考虑求解两个子数组A[low..high]的任何连续子数组A[i..j]所处的位置必然是以下三种情况之一：
- 完全位于子数组A[low, mid]中，因此，low <= i <= j <= mid
- 完全位于子数组A[mid+1, high]中，因此mid <= i <= j <= high
- 跨越了重点，因此low <= i <= mid < j <= high
递归地求解A[low..mid]和A[mid+1..high]的最大子数组，因为这两个子问题仍然是最大子数组问题，只是规模更小
伪代码
注意求出跨越中点的最大子数组问题并非原问题的更小实例，因为它加入了限制，求出的子数组必须跨越中点，任何跨越中点的子数组都由两个子数组A[i..mid]和A[mid+1..j]组成，其中low<= i <= mid且mid< j <= high，因此，只需要找出形如A[i..mid]和A[mid+1..j]的最大子数组，然后将其合并即可，过程FIND-MAX-CORSSING-SUBARRAY接收数组A和下标low, mid和high为输入，返回一个下标元组划定跨越中点的最大子数组的边界，并返回最大子数组中值的和
先求出左半部A[low..mid]的最大子数组，再求出右半部A[mid+1..high]的最大子数组，然后返回子数组A[max-left..max-right]
FIND-MAX-CORSSING-SUBARRAY(A, low, mid, high) left-sum = A[mid] sum = 0 for i = mid downto low sum = sum + A[i] if sum > left-sum left-sum = sum max-left = i right-sum = A[mid+1] sum = 0 for j = mid+1 to high sum += A[j] if sum > right-sum right-sum = sum max-right = j return (max-left, max-right, left-sum+right-sum)
求解最大子数组问题的分治算法的伪代码：
FIND-MAXIMUM-SUBARRAY(A, low, high) if high == low return(low, high, A[low]) else mid = (low + high) / 2 (left-low, left-high, left-sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid) (right-low, right-high, right-sum) = FIND-MAXIMUM-SUBARRAY(A, mid+1, high) (cross-low, corss-high, cross-sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high) if left-sum >= right-sum and left-sum >= corss-sum return (left-low, left-high, left-sum) else if right-sum >= left-sum and right-sum >= cross-sum return (right-low, right-high, right-sum) else return (corss-low, cross-high, cross-sum)
C语言代码实现
#include<stdio.h> #define LEN(array) (sizeof(array)/sizeof(array[0])) int maxsubarray(int *, int , int , int *, int *); int crosssubarray(int *array, int low, int mid, int high, int *begin, int *end); main(){ int array[] = {13, -3, -25, 20, -3, -16, 23, -18, -20, -7, 12, -5, -22, 15, -4}; int i, start, end, sum; printf("原始数组:\n"); for (i = 0; i < LEN(array); i++) printf("%5d", array[i]); putchar('\n'); sum = maxsubarray(array, 0, LEN(array)-1, &start, &end); printf("最大子序列的和为：%d\n", sum); printf("最大子序列的起始位置为：%d, 终止位置为：%d\n", start+1, end+1); printf("最大子序列为: "); for (i = start; i <= end; i++) printf("%5d", array[i]); putchar('\n'); putchar('\n'); } int maxsubarray(int *array, int low, int high, int *begin, int *end){ int mid, left_sum, right_sum, cross_sum; int left_low, left_high, right_low, right_high, cross_low, cross_high; if (low == high){ return array[low]; *begin = low; *end = high; } mid = (low + high) / 2; left_sum = maxsubarray(array, low, mid, begin, end); left_low = *begin; left_high = *end; right_sum = maxsubarray(array, mid+1, high, begin, end); right_low = *begin; right_high = *end; cross_sum = crosssubarray(array, low, mid, high, begin, end); cross_low = *begin; cross_high = *end; if (left_sum > right_sum && left_sum > cross_sum){ *begin = left_low; *end = left_high; return left_sum; } else if (right_sum > left_sum && right_sum > cross_sum){ *begin = right_low; *end = right_high; return right_sum; } else{ *begin = cross_low; *end = cross_high; return cross_sum; } } int crosssubarray(int *array, int low, int mid, int high, int *begin, int *end){ int left_sum, right_sum, sum, i, j; left_sum = array[mid]; sum = 0; *begin = mid; *end = mid+1; for (i = mid; i >= low; i--){ sum += array[i]; if (sum > left_sum){ left_sum = sum; *begin = i; } } right_sum = array[mid+1]; sum = 0; for (j = mid+1; j <= high; j++){ sum += array[j]; if (sum > right_sum){ right_sum = sum; *end = j; } } return left_sum + right_sum; }
运行时间为θ(n)
只使用了一次for循环，注意，该算法只适用于数组原来的所有元素的求和值大于0，如果原来的数组的所有元素的求和值小于0,则不适用于本算法
C语言代码实现
#include<stdio.h> #define LEN(array) (sizeof(array)/sizeof(array[0])) void maxsubarray(int *array, int len, int *, int *); main(){ // int array[] = {13, -3, -25, 20, -3, -16, 23, -18, -20, -7, 12, -5, -22, 15, -4}; // int array[] = {13, -3, -25}; int array[] = {13, -3, -25, 55, -34}; int i, start, end; printf("原始数组:\n"); for (i = 0; i < LEN(array); i++) printf("%5d", array[i]); putchar('\n'); maxsubarray(array, LEN(array), &start, &end); printf("最大子序列的起始位置为：%d, 终止位置为：%d\n", start+1, end+1); printf("最大子序列为: "); for (i = start; i <= end; i++) printf("%5d", array[i]); putchar('\n'); putchar('\n'); } void maxsubarray(int *array, int len, int *start, int *end){ int i, sum, maxsum, temp;
sum = maxsum = 0; temp = 0; for (i = 0; i < len; i++){ sum += array[i]; if (sum > maxsum){ maxsum = sum; *end = i; *start = temp; } else if (sum < 0){ //temp的值就是最大子序列的起始位置 sum = 0; temp = i + 1; } } printf("\n子序列的求和最大值为： %d\n", maxsum); }