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:
#include <stdio.h> #define MAX_INX 50010
#define Max(a,b) (a)>(b)?(a):(b) int max_sum2(int *pData, int cnt)
{
// DP: Max sum of sub-sequence: dp[i] = MAX(num[i], dp[i-1] + num[i]) // Left -> Right
int lt[MAX_INX] = { };
lt[] = pData[];
for (int i = ; i < cnt; i ++)
{
lt[i] = Max(pData[i], lt[i - ] + pData[i]);
} // Right -> Left
int rt[MAX_INX] = { };
int rtm[MAX_INX] = { };
rt[cnt-] = pData[cnt-];
for (int i = cnt-; i >= ; i--)
{
rt[i] = Max(pData[i], rt[i + ] + pData[i]);
}
rtm[cnt-] = rt[cnt-];
for (int i = cnt-; i >=; i--)
{
rtm[i] = Max(rtm[i+], rt[i]);
} // O(n) to find real max
int ret = -;
for (int i = ; i < cnt - ; i ++)
{
ret = Max(ret, lt[i] + rtm[i+]);
} return ret;
} int main()
{
int nTotal = ;
scanf("%d", &nTotal); while (nTotal--)
{
int num[MAX_INX] = { }; // Get Input
int nCnt = ; scanf("%d", &nCnt);
for (int i = ; i < nCnt; i ++)
{
scanf("%d", num + i);
} printf("%d\n", max_sum2(num, nCnt));
} return ;
}