首页 > 代码库 > POJ 1050 To the Max DP题解
POJ 1050 To the Max DP题解
一维最大字段和的扩展。
要诀是固定列的左右点,比如左边记录为left, 右边记录为right,那么一个循环left从0到COL,行最大值,那么right从left开始循环到COl,就可以考虑到所有列组合了,这个循环是O(n*n),然后求范围列内的行最大子段和,时间是O(n),
这样巧妙地把二维的问题转化为一维了,最终时间复杂度是O(n^3)。
可以参考Geeks上的讲解,不过他的最大子段和代码写的挺挫的,我的代码会简洁很多,而且也考虑到了负值情况了。
Geeks地址:http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/
#include <stdio.h> #include <string.h> #include <limits.h> const int MAX_N = 100; int N; int arr[MAX_N][MAX_N]; int temp[MAX_N]; inline int max(int a, int b) { return a > b ? a : b; } int kadane(int *A, int n) { int sum = 0, maxSum = INT_MIN, i; for (i = 0; i < n; i++) { sum += A[i]; maxSum = max(sum, maxSum); sum = max(sum, 0); } return maxSum; } int maximalSubRetangle() { int maxSum = INT_MIN; int left, right, i; for (left = 0; left < N; left++) { memset(temp, 0, sizeof(int) * N); for (right = left; right < N; ++right) { for (i = 0; i < N; i++) { temp[i] += arr[i][right]; } maxSum = max(maxSum, kadane(temp, N)); } } return maxSum; } int main() { while (scanf("%d", &N) != EOF) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d", &arr[i][j]); } } printf("%d\n", maximalSubRetangle()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。