今天做了这题是找出两个区间的最大和，感觉和一个差不多，不过跑的很慢，下面是我的代码
1 #include<iostream>
2 using namespace std;
3 int t, n, ma, a[100000], ans[50030];
4
5 inline int max(int a, int b){
6 return a > b ? a : b;
7 }
8
9 int main(){
10 for (scanf("%d", &t); t--;){
11 scanf("%d", &n);
12 for (int i = 0; i < n; i++)scanf("%d", a + i);
13 ans[0] = a[0];
14 for (int i = 1; i < n; i++) ans[i] = max(ans[i - 1] + a[i], a[i]);
15 int ret = ans[n - 2] + a[n - 1];
16 int q2 = a[n - 1], q1 = a[n - 1];
17 for (int i = n - 2; i > 0; i--){
18 q2 = max(q2, q1);
19 q1 = max(a[i], a[i] + q1);
20 ret = max(ret, ans[i - 1] + max(q1, q2));
21 }
22 printf("%d\n", ret);
23 }
24 }
写的比较恶心，所以去网上找了些资料，来重新思考下
————————————————————————————————————————————————————————
最大子序列和线性算法
问题描述：
给定整数A1， A2，……AN （可能有负数），求I到j的最大值。
例如：
-2, 11, -4, 13, -5, -2时答案为20
对于这个问题的算法有很多，当然我要说的是使用“动态规划”算法实现的程序，对于这个算法，我可以说很多人都曾经想到，但是没有想全（因为我就是这样的）。还有一点对于这个问题的动态规划的解法是非常经典的，她的时间复杂度是O(n),也就是线性的。而对于穷举法它的时间复杂度可是O(n3), 这样看来可以巨大的改进了。
考虑这样的一个问题，我们从最简单的左边开始看，就如上面的例子，-2对于结果有影响吗？回答是没有。那么让我们看下面这样一个例子：
6, -7, ……
此时，我们还需要考虑6 和 –7 吗，有些人说要的，因为可能对于6，后面没有比其更大的了，是啊。问题是这样的。那么对于后面的结果分析其有影响吗？这个时候我们可以说没有影响的！
到现在，上面是不是大家多曾经想到了呢？呵呵，我曾经就想到了，那我们为什么不把这问题，推倒后面呢？动态规划法就是解决这样的一个问题，我们知道此时前面的两个数就是一种最优的子结构（尽管只有2个数，不过是完全可以推广的。）
书中的算法就告诉我们是如何推广的，我写这样的一篇文章的具体目的也就是为了说明以上的问题，因为我和大家一样都曾经想到了前面的算法，却没有考虑下去。以此感慨！并遗憾！
那么书中的算法是这样的：（看这个算法之前应该先知道这个问题的“分治法”的求解，这样更让你觉得，这个算法的完美之处。）
Int MaxSubsequenceSum(const int A[], int N)
{
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
For(j=0; j < N; j++)
{
ThisSum += A[j];
If (ThisSum > MaxSum)
MaxSum = ThisSum;
Else if(ThisSum < 0)
ThisSum = 0;
}
return MaxSum;
}
对于这个算法的分析(逻辑):
从左相右相加，若结果不断的增加，那么ThisSum将同MaxSum一起增加，如果遇到负数，那么也加到ThisSum上去，但是此时ThisSum < MaxSum，那么就不加。看ThisSum是不是会回升，若一直不回升，不断或是波浪型的下降，那么当它降到0时，说明前一段与后一段是可以抛弃的。正如有 7 ， -8 一样，我们可以不要这两个数，但是我们知道MaxSum依然保存着前一段的最大值，（这就是这个算法中的厉害，我认为）。然后，ThisSum将从后面开始将这个子段进行分析，若有比当前MaxSum大的子段，然后替换（此时可以彻底抛弃前一段）。这样一趟扫描结果也就出来了。
后记：
对于这个问题，一开始对于分治算法，我们可能很容易想对，而对与动态规划可能我们很难想到（至少我没有那么轻易就想到了）。尽管如此，还是比较庆幸想到了其最优子结构，问题解决到此，当然对于这个问题，我们还是可以用“分治”算法，其时间复杂度为:O(nlogn)，也是比较优的，当然没有上面提到的优。
————————————————————————————————————————————————————————
PS：上面的上算法课时学过了。
————————————————————————————————————————————————————————
Pku acm 1050 To the Max 动态规划题目解题报告(十六) 收藏
http://acm.pku.edu.cn/JudgeOnline/problem?id=1050
题目的意思很简单，在一个矩阵里面找它的子矩阵，使得子矩阵数值之和到达最大。其实就是最大子段和问题在二维空间上的推广。先说一下一维的情况吧：设有数组a0,a1…an,找除其中连续的子段，使它们的和达到最大。假如对于子段：9 2 -16 2 temp[i]表示以ai结尾的子段中的最大子段和。在已知temp[i]的情况下，求temp [i+1]的方法是：
如果temp[i]>0 temp [i+1]= temp[i]+ai(继续在前一个子段上加上ai),否则temp[i+1]=ai(不加上前面的子段)，也就是说 状态转移方程：
temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];
对于刚才的例子 temp： 9 11 -5 2，然后取temp[]中最大的就是一维序列的最大子段。求一维最大子段和的函数：
int getMax(int buf[100],int n)
{
int temp[101],max=n*(-127);
memset(temp,0,4*(n+1));
for(int i=1;i<=n;i++)
{
temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];
if(max<temp[i])
max=temp[i];
}
return max;
}
下面扩展到二维的情况：考察下面题目中的例子：
0 -2 -7 0
9 2 -6 2
-4 1 -4 7
-1 8 0 -2
我们分别用i j表示起始行和终止行，遍历所有的可能：
for(i=1;i<=n;i++)
for(j=i;j<=n;j++) {}
我们考察其中一种情况 i=2 j=4，这样就相当与选中了2 3 4三行，求那几列的组合能获得最大值，由于总是 2 3 4行，所以我们可以将这3行”捆绑”起来，变为求 4(9-4-1),11(8+2+1),-10(-6-4+0),7(7+2-2)的最大子段和，ok，问题成功转化为一维的情况！
带有详细注释的代码可以在http://download.csdn.net/user/china8848/获得
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/china8848/archive/2008/01/03/2015984.aspx
————————————————————————————————————————————————————————
PS：这是二维的。。