poj-2593

#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的一个优势： 不会反复求解重叠子问题.