问题引出:
编程找出指定数列的所有子列和的最大值;
假定数列:
int arry[16] = {5, -6, 4, -5, 3, 1, 2, -4, 8, -9, 3, 1, -7, 6, 4, -1};
算法一:
#include <iostream> using namespace std; int main() { const int N = 16; int arry[N] = {5, -6, 4, -5, 3, 1, 2, -4, 8, -9, 3, 1, -7, 6, 4, -1}; int maxsum = 0; for (int k = 0; k < N; k++) { for (int j = k; j < N; j++) { int tempsum = 0; for (int i = k; i <= j; i++) { tempsum += arry[i]; } maxsum = tempsum > maxsum ? tempsum : maxsum; } } cout << maxsum << endl; return 0; }
例用三个循环:其时间复杂度T(N) = O(N3);
算法二:
#include <iostream> using namespace std; int main() { const int N = 16; int arry[N] = {5, -6, 4, -5, 3, 1, 2, -4, 8, -9, 3, 1, -7, 6, 4, -1}; int maxsum = 0; for (int k = 0; k < N; k++) { int tempsum = 0; for (int j = k; j < N; j++) { tempsum += arry[j]; maxsum = tempsum > maxsum ? tempsum : maxsum; } } cout << maxsum << endl; return 0; }
例用两个循环:其时间复杂度T(N) = O(N2);
算法三:
算法四:
线性表: