Hi, I'm back.
This is a realy classic DP problem to code.
1. You have to be crystal clear about what you are going to solve.
2. Apparently there are 2 DP sections
3. Think carefully about recurrence relations
5. Details: take care of indices boundaries - it costed me 1hr to find an indexing bug!
6. Again: think crystal clear before you code!
And, #2593 is exactly the same.
Here is my AC code:
1 #include <stdio.h> 2 3 #define MAX_INX 50010 4 #define Max(a,b) (a)>(b)?(a):(b) 5 6 int max_sum2(int *pData, int cnt) 7 { 8 // DP: Max sum of sub-sequence: dp[i] = MAX(num[i], dp[i-1] + num[i]) 9 10 // Left -> Right 11 int lt[MAX_INX] = { 0 }; 12 lt[0] = pData[0]; 13 for (int i = 1; i < cnt; i ++) 14 { 15 lt[i] = Max(pData[i], lt[i - 1] + pData[i]); 16 } 17 18 // Right -> Left 19 int rt[MAX_INX] = { 0 }; 20 int rtm[MAX_INX] = { 0 }; 21 rt[cnt-1] = pData[cnt-1]; 22 for (int i = cnt-2; i >= 0; i--) 23 { 24 rt[i] = Max(pData[i], rt[i + 1] + pData[i]); 25 } 26 rtm[cnt-1] = rt[cnt-1]; 27 for (int i = cnt-2; i >=0; i--) 28 { 29 rtm[i] = Max(rtm[i+1], rt[i]); 30 } 31 32 // O(n) to find real max 33 int ret = -10010; 34 for (int i = 0; i < cnt - 1; i ++) 35 { 36 ret = Max(ret, lt[i] + rtm[i+1]); 37 } 38 39 return ret; 40 } 41 42 int main() 43 { 44 int nTotal = 0; 45 scanf("%d", &nTotal); 46 47 while (nTotal--) 48 { 49 int num[MAX_INX] = { 0 }; 50 51 // Get Input 52 int nCnt = 0; scanf("%d", &nCnt); 53 for (int i = 0; i < nCnt; i ++) 54 { 55 scanf("%d", num + i); 56 } 57 58 printf("%d ", max_sum2(num, nCnt)); 59 } 60 61 return 0; 62 }