最大子段和算法分析
问题:
给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0,依此定义,所求的最优值为:
Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如,当(a1,a2,a3,a4,a4,a6)=(-2,11,-4,13,-5,-2)时,最大子段和为20 下面列出了四种计算方式,时间复杂度各逐渐变小,其中动态规划法时间复杂度最小。
/** * @brief 最大子段和,穷举法,时间复杂度O(n^3) * */ int MaxSum(int* A, int n) { int sum = 0; for (int i = 0; i < n; ++i) { for (int j = i; j < n; ++j) { int thissum = 0; for (int k = i; k <= j; ++k) { thissum += A[k]; } if (thissum > sum) { sum = thissum; } } } return sum; } /** * @brief 最大子段和,穷举法改进,时间复杂度O(n^2) * */ int MaxSumEx(int* A, int n) { int sum = 0; for (int i = 0; i < n; ++i) { int thissum = 0; for (int j = i; j < n; ++j) { thissum += A[j]; if (thissum > sum) { sum = thissum; } } } return sum; } /** * @brief 最大子段和,分治法,时间复杂度O(nlogn) * * 将a[1n]分成a[1n/2]和a[n/2+1n],则a[1n]的最大字段和有三种情况: * (1)a[1n]的最大子段和与a[1n/2]的最大子段和相同 * (2)a[1n]的最大子段和与a[n/2n]的最大子段和相同 * (3)a[1n]的最大子段和为ai++aj,1<=i<=n/2,n/2+1<=j<=n * T(n)=2T(n/2)+O(n) * T(n)=O(nlogn) */ int MaxSum_DIV(int* A, int left, int right) { int sum = 0; if (left == right) { sum = A[left] > 0 ? A[left] : 0; } else { int center = (left + right) / 2; int leftMax = MaxSum_DIV(A, left, center); int rightMax = MaxSum_DIV(A, center + 1, right); int s1 = 0, leftSum = 0; for (int i = center; i >= left; --i) { leftSum += A[i]; if (leftSum > s1) { s1 = leftSum; } } int s2 = 0, rightSum = 0; for (int j = center + 1; j <= right; ++j) { rightSum += A[j]; if (rightSum > s2) { s2 = rightSum; } } sum = s1 + s2; if (leftMax > sum) { sum = leftMax; } if (rightMax > sum) { sum = rightMax; } } return sum; } /* @brief 最大子段和,动态规划法,时间复杂度O(n) * b[j]=max{a[i]++a[j]},1<=i<=j,且1<=j<=n,则所求的最大子段和为max b[j],1<=j<=n。 * 由b[j]的定义可易知,当b[j-1]>0时b[j]=b[j-1]+a[j],否则b[j]=a[j]。故b[j]的动态规划递归式为: * b[j]=max(b[j-1]+a[j],a[j]),1<=j<=n。 * T(n)=O(n) */ int MaxSum_DYN(int* A, int n) { int sum = 0; int b = 0; for (int i = 0; i < n; ++i) { if (b > 0) { b += A[i]; } else { b = A[i]; } if (b > sum) { sum = b; } } return sum; } int main() { int A[6] = {-2,11,-4,13,-5,-2}; cout << MaxSum(A, 6) << endl; cout << MaxSumEx(A, 6) << endl; cout << MaxSum_DIV(A, 0, 5) << endl; cout << MaxSum_DYN(A, 6) << endl; }