POJ - 2479 Maximum sum解题报告

给你你一串数（50,000）个,让你从这一大串数中找出连续的两串数，使得其和最大。

设：以第i个数为结尾的串可能的最大的连续子串为a[i];后j个数中能选出的最大的连续子串为b[j];

对于a数组的递推关系（b数组同理）：

2.现在就是要找到a[i]+b[j](i+j<=n)的最大值了，但是暴力O(n^2)又超时了，所以还是空间换时间。aa[i]表示a[1]-a[i]之间的最大值，bb[i]表示b[1]-b[i]之间的最大值，然后找到max{aa[i]+bb[n-i]}(1<=i<=n)即为结果;三个操作都是O(n);