1 对于O(N*N)的解法就不必说了,简单粗暴
2 对于ON(logN)的解法
例如 { -1 2 3 -3 -4 5 -4 6 8 3 -5}这个序列,求他的最小子序列
1 设S[0] = 0; 这个是为了更好的区分下表
则有 S[1] = A[1]+S[0]
S[2] =A[2]+S[1]
可以推出任意子序列都可以表示两个序列之差
S[j]-S[i]=A[j]+A[j-1]+A[j-2]+....+A[i+1]+S[i]-S[i]
=A[j]+...A[i+1]
所以这个算法分3部
1 算出S[i]
2 对S[i]排序(是为了相邻的两个子序列更小
3 求差(下标要符合序列不能S[i]-S[j]
/*求最小正子序列和*/ #include <stdio.h> //定义结构体 struct An{ int S; int num; }; //O(N*N*N) int funca(int *arry, int num) { int i,j,k; int sum,thissum; sum = 0; for(i = 0; i< num; i++) { if(arry[i] > 0) { sum = arry[i]; break; } } if(sum == 0) { printf("没有正子项！\n"); return 0; } for(i = 0; i<num; i++) { for(j = i; j<num;j++) { thissum = 0; for(k = j; k <num; k++) { thissum+=arry[k]; if(thissum<sum && thissum > 0) { sum = thissum; } } } } return sum; } //O(N*N) int funcb(int *arry, int num) { int i,j; int sum,thissum; sum = 0; for(i = 0; i< num; i++) { if(arry[i] > 0) { sum = arry[i]; break; } } if(sum == 0) { printf("没有正子项！\n"); return 0; } for(i = 0; i<num; i++) { thissum = 0; for(j = i; j<num; j++) { thissum+=arry[j]; if(thissum < sum && thissum > 0) { sum = thissum; } } } return sum; } int minthree(int num1, int num2, int num3) { return ((num1>num2) ? num2:num1) > num3 ? num3:((num1>num2)?num2:num1); } //排序 随便写了一个冒泡排序,相同元素的下标要合并为其中最小的一个 void sort(struct An* A, int num) { int i,j; struct An Atemp; for(i = 0; i<num; i++) { for(j = 0; j<num-i-1; j++) { if(A[j].S > A[j+1].S) { Atemp.S = A[j].S; Atemp.num = A[j].num; A[j].S = A[j+1].S; A[j].num = A[j+1].num; A[j+1].S = Atemp.S; A[j+1].num = Atemp.num; } } } for(i = 0; i< num-1;i++) { if(A[i].S == A[i+1].S) { j = (A[i].num > A[i+1].num ? A[i+1].num:A[i].num); A[i].num = j; A[i+1].num = j; } } } //O(NlogN) int funcc(int *arry, int num) { struct An A[num+1]; int i = 0; int thissum = 0; int sum = 100; //填0占位 A[0].S = 0; A[0].num = 0; //求出序列S和 for(i = 1; i<num+1; i++) { A[i].S = arry[i-1] + A[i-1].S; A[i].num = i; } //排序 sort(A, num+1); //计算相邻两个之间的最小值(必须保证num也是符合序列的) for(i = 0; i<num; i++) { thissum = A[i+1].S-A[i].S; if(thissum < sum && (A[i+1].num > A[i].num)) { sum = thissum; } } return sum; } int main() { // int arry[10] = { 4, 3, 5, -2, -1, 2, 6, -2, -10, 9}; // int a = funca(arry, 10); // int b = funcb(arry, 10); // int c = funcc(arry, 10); int arry[5] = {4, 0, 4, 1, -1}; int c = funcc(arry, 5); // printf("a = %d\n", a); // printf("b = %d\n", b); printf("c = %d\n", c); return 0; }
