POJ-2593的解题思路有哪些？

本文共计744个文字，预计阅读时间需要3分钟。

伪原创以下开头内容，要求不重复，不超过100字，直接输出结果：

以下是对原文的开头进行伪原创改写，确保内容不雷同，字数控制在100字以内，请查看结果。

#include <stdio.h> #include <malloc.h> int getMaxSum(int *array, int beginPos, int endPos, int *dpArray) { int MaxBegin = beginPos; int MaxEnd = beginPos; int curMax = array[beginPos]; int curMaxAlignRight = array[beginPos]; int curMaxAlignRightBegin = beginPos; dpArray[beginPos] = curMax; for (int i = beginPos+1; i <= endPos; i++) { if (curMaxAlignRight > 0) { if (array[i] + curMaxAlignRight > curMax) { curMax = array[i] + curMaxAlignRight; MaxBegin = curMaxAlignRightBegin; MaxEnd = i; } else { } curMaxAlignRight = curMaxAlignRight + array[i]; } else { if (array[i] > curMax) { curMax = array[i]; MaxBegin = i; MaxEnd = i; } curMaxAlignRight = array[i]; curMaxAlignRightBegin = i; } dpArray[i] = curMax; } return curMax; } int getMaxSumReverse(int *array, int beginPos, int endPos, int *dpArray) { int MaxBegin = beginPos; int MaxEnd = beginPos; int curMax = array[beginPos]; int curMaxAlignRight = array[beginPos]; int curMaxAlignRightBegin = beginPos; dpArray[beginPos] = curMax; for (int i = beginPos - 1; i >= endPos; i--) { if (curMaxAlignRight > 0) { if (array[i] + curMaxAlignRight > curMax) { curMax = array[i] + curMaxAlignRight; MaxBegin = curMaxAlignRightBegin; MaxEnd = i; } else { } curMaxAlignRight = curMaxAlignRight + array[i]; } else { if (array[i] > curMax) { curMax = array[i]; MaxBegin = i; MaxEnd = i; } curMaxAlignRight = array[i]; curMaxAlignRightBegin = i; } dpArray[i] = curMax; } return curMax; } void getD(int * array, int length) { int firstPostivePos = 0; int lastPostivePos = length-1; int initLeftMax = 0;//array[firstPostivePos]; int leftUnusedAcc = 0; int rightMax = array[lastPostivePos]; int rightAcc = array[lastPostivePos]; int rightMaxLeftBound = lastPostivePos; int MaxSum = -10001; int * leftDPArray = (int *) malloc(length * sizeof(int)); int * rightDPArray = (int *) malloc(length * sizeof(int)); getMaxSum(array, firstPostivePos, lastPostivePos, leftDPArray); // for (int i = 0; i < length; i++) { // printf("%d ", leftDPArray[i]); // } // printf("\n"); getMaxSumReverse(array, lastPostivePos, firstPostivePos, rightDPArray); // for (int i = 0; i < length; i++) { // printf("%d ", rightDPArray[i]); // } // printf("\n"); for (int i = firstPostivePos; i <= lastPostivePos - 1; i++) { int leftMaxSum = leftDPArray[i]; int rightMaxSum = rightDPArray[i+1]; if (leftMaxSum + rightMaxSum > MaxSum) { MaxSum = leftMaxSum + rightMaxSum; } } printf("%d\n", MaxSum); free(leftDPArray); leftDPArray = NULL; free(rightDPArray); rightDPArray = NULL; return; } int main() { while(1) { int num; scanf("%d", &num); if (num == 0) { return 0; } int * array = (int *)malloc(num * sizeof(int)); int postiveNum = 0; int maxValue = -10001; for (int i = 0; i < num; i ++) { char tmp; scanf("%d%c", array + i, &tmp); if (*(array + i) > 0) { postiveNum++; } if (*(array + i) > maxValue) { maxValue = *(array + i); } } getD(array, num); free(array); array = NULL; } }

同2479, 买一送一.

一开始还想着整个用DP求出来，

结果最后一步却应该是枚举。

算法导论DP那一章举的矩阵乘法例子和这个有点像(那道题就是枚举了从i到j的所有可能结果， 然后求代价最小的)， 但还是有显著不一样的

在那个例子中， 所有的问题都有同样的结构， 即都可进行分割， 然后求两个分割部（好可以分割）的最优解。

本题的特殊在于： 第一次分割以后， 子问题的结构就和父问题的结构不一样了（父问题是求两个连续区间的最大和，而子问题则变为了

求此区间的最大连续和）。

DP在本题的优势就在于，在分别从左到右 和 从右向左分别求出 a[1~ i] (i <= length -2) 和 a[j~length-1](j >=2) 区间内的最大连续和， 只需一次遍历，

在DP的步进式推倒中， 一个一个局部最优解被求了出来。

这也显出了DP的一个优势： 不会反复求解重叠子问题.