/* coding=UTF-8 */ #include <stdio.h> #include <limits.h> #define MAX_LENGTH 1000 #define MAX(a, b) ((a) > (b) ? (a) : (b)) int errno; /* 求一维数组最大连续和 */ int max_subarray(int *a, int len) { errno = 0; if (NULL == a || len < 1) { errno = 1; return 1; } int max = a[0], i, sum = a[0]; for (i = 1; i < len; i++) { if (sum < 0) { sum = a[i]; } else { sum += a[i]; } max = MAX(max, sum); } return max; } /* 求一个数组的两段连续的部分的最大和 * 输入一个数组a,以及长度len * 思路:先把a分成前后两部分,分别求两部分的最大连续和 * 依次遍历求得两个子数组的最大连续和最大即为所求 */ int op(int *a, int len) { errno = 0; /* 输入异常处理 */ if (NULL == a || len < 2) { errno = 1; return 0; } int i, max = INT_MIN; for (i = 1; i < len; i++) { int t1 = max_subarray(a + i, len - i); int t2 = max_subarray(a, i); max = MAX(max, t1 + t2); } return max; } int main(int argc, char **argv) { int a[] = {1,-2,2,3,-4}; int b[] = {-1, -1, -1, -1}; int c[] = {-1, 1}; printf("%d\n", op(a, 5)); printf("%d\n", op(b, 4)); printf("%d\n", op(c, 2)); return 0; }
2023年4月23日 19:41
crediblebh