給你你一串數（50,000）個,讓你從這一大串數中找出連續的兩串數，使得其和最大。
思路：首先，三十組測試數據，每組規模50,000，時間復雜度肯定不能是O(n^2)了
設：以第i個數為結尾的串可能的最大的連續子串為a[i];后j個數中能選出的最大的連續子串為b[j];
對于a數組的遞推關系（b數組同理）：
遞推關系：a[i]=max(v[i],a[i-1]+v[i]);邊界條件：a[1]=v[1];實現過程：1.首先一次dp存到a數組，然后給v數組倒置，再一次dp存到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);
新聞熱點
疑難解答
