输入一组整数，求出这组数字子序列和中最大值。也就是只要求出最大子序列的和，不必求出最大的那个序列。例如：
序列：-2 11 -4 13 -5 -2，则最大子序列和为20。
序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为16。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
#include <stdio.h> #include <time.h> #define NUM 10 void displayarray(int a[], int n); //display arrays on screen int initarray(int *p, int n); //give random values to the array int maxsum1(int a[], int n); //O(n^2) int maxsum2(int a[], int left, int right); //O(nlogn) int maxsum3(int a[], int n); //O(n) int max3(int, int, int); //return the max number of the three int main(void) { int i, cho; int a[NUM]; initarray(a, NUM); displayarray(a, NUM); while(1) { printf("please choose a algroithm\n"); printf("1. O(n^2)\n"); printf("2. O(nlogn)\n"); printf("3. O(n)\n"); scanf("%d", &cho); switch(cho) { case 1: printf("the maxsub id %d\n", maxsum1(a, NUM)); break; case 2: printf("the maxsub id %d\n", maxsubsum2(a, NUM)); break; case 3: printf("the maxsub id %d\n", maxsum3(a, NUM)); break; default: break; } } return 0; } int initarray(int *p, int n) { int i; srand((int)time(NULL)); for (i = 0; i < n; i++) { p[i] = rand() % 20 - 10; } return 1; } void displayarray(int a[], int n) { int i; for (i = 0; i < n; ++i) { printf("%d\t", a[i]); } } int maxsum1(int a[], int n) { int i, j; int tempsum; int maxsum = 0; for (i = 0; i < n; i++) { tempsum = 0; for (j = i; j < n; j++) { tempsum += a[j]; if (tempsum > maxsum) { maxsum = tempsum; } } } return maxsum; } int maxsum2(int a[], int left, int right) { int maxleftsum, maxrightsum; int maxleftbordersum, maxrightbordersum; int leftbordersum, rightbordersum; int center, i; if (left == right) //base case { if (a[left] > 0) return a[left]; else return 0; } center = (left + right) / 2; maxleftsum = maxsum2(a, left, center); maxrightsum = maxsum2(a, center+1, right); maxleftbordersum = 0; leftbordersum = 0; for (i = center; i >= left; i--) { leftbordersum += a[i]; if (leftbordersum > maxleftbordersum) maxleftbordersum = leftbordersum; } maxrightbordersum = 0; rightbordersum = 0; for (i = center + 1; i <= right; i++) { rightbordersum += a[i]; if (rightbordersum > maxrightbordersum) maxrightbordersum = rightbordersum; } return max3(maxleftsum, maxrightsum, maxleftbordersum + maxrightbordersum); } int maxsum3(int a[], int n) { int i; int tempsum, maxsum; tempsum = 0; maxsum = 0; for (i = 0; i < n; i++) { tempsum += a[i]; if (tempsum > maxsum) maxsum = tempsum; if (tempsum < 0) tempsum = 0; } return maxsum; } int max3(int a, int b, int c) { int two; two = a > b ? a : b; return two > c ? two : c; } int maxsubsum2(int a[], int n) { return maxsum2(a, 0, n-1); } |
支付宝打赏 
微信打赏