想了一会之后,找到了一个转化为最大连续子序列的办法。也就是先对列求和,之后再用最大连续子序列的方法。给出这个办法后,还想考虑优化,只是一直想不出来。回来之后,想起编程之美上有类似的题目,看了之后,没想到已经是最优的了。又想起以前在POJ应该做过类似的题目,于是找到了POJ1050- To The Max. 编写代码如下:
#include<stdio.h> #include<stdlib.h> #define N 100 int a[N][N]; int b[N]; intmax_sub_array(int *a, int n){ int max_sum = a[0]; int sum = a[0]; for (int i = 1; i < n; i++) { if (sum < 0) { sum = 0; } sum += a[i]; if (sum > max_sum) { max_sum = sum; } } return max_sum; } intmain(){ int n; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &a[i][j]); } } int max_sum = -127 * 100 * 100; for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { b[k] = 0; } for (int j = i; j < n; j++) { for (int k = 0; k < n; k++) { b[k] += a[j][k]; } int sum = max_sub_array(b, n); if (sum > max_sum) { max_sum = sum; } } } printf("%d\n", max_sum); return0; }