最大连续子数列和有关问题

最大连续子数列和问题
以下这个采用分治法的递归算法我有些不太明白的地方：

C/C++ code

//采用分治递归策略的算法3，效率为o(nlogn)   long long f3(int left,int right)   {       if(left > right)return 0;       if(left == right)return a[left];              int m = (left+right)/2;       long long lmax = a[left];       long long rmax = a[m+1];       long long tmp = 0;         for(int i = m;i >= left;i--){           tmp += a[i];           if(tmp > lmax) lmax = tmp;       }       tmp = 0;       for(int i = m+1;i <= right;i++){           tmp += a[i];           if(tmp > rmax) rmax = tmp;       }       return max(lmax+rmax,f3(left,m),f3(m+1,right));   }   

分析数据如下：

C/C++ code

 -9 9 -2 5 -25 11 2 -9 7 -1 3 -6

通过二分法，被分成两个部分，

C/C++ code

 -9 9 -2 5 -25 11 

这一部分的最大连续子数列的和应该为12

C/C++ code

 2 -9 7 -1 3 -6

这一部分的最大连续子数列和应该为9


而整个序列的最大连续子数列的和是否应该是11+2 =13

Q1.但这个序列被人为地分成两部分后，似乎并没有处理其中间相邻的连续部分

Q2.还有我感觉两个for语句只能求出一个左右两部分的总和而已？似乎并不能求出子部分的最大和。


[解决办法]
有DP算法,简单高效
[解决办法]

C/C++ code

b=a[0];max=b;for(i=1;i<n;i++){  if (b>0) then      b+=a[i]  else      b=a[i];  if (b>max) then max=b;}
[解决办法]
http://blog.csdn.net/g_idea/archive/2009/09/03/4514913.aspx
[解决办法]
>而整个序列的最大连续子数列的和是否应该是11+2 =13
乃没看懂这句return max(lmax+rmax,f3(left,m),f3(m+1,right));。lmax+rmax可不是乃的11+2。
[解决办法]
最长连续，用DP的方法就是：
重要信息：数列是连续的！ 对于第n个数字来说，只有2种选择要么加入第n-1的那个序列里，要么从新以这里做源头来开始一个新的数列，也就是说如果第n+1个数字加进去以后比它本身的要大的话就说明还可以继续加入进去，如果加入第n+1个数字居然比单单一个n+1数字还小的话那还继续干什么？？
那么对于第n个数字来说就是：
f(n) = max{f(n-1)+arr[n], arr[n]}

C/C++ code
#include <iostream>using namespace std;int arr[] = {-9, 9, -2, 5, -25, 11, 2, -9, 7, -1, 3, -6};void f(){    int curNum;    int max;    max = curNum = arr[0];    for(int i=1; i<sizeof(arr)/sizeof(int); i++)    {        if(arr[i]+curNum > arr[i])            curNum = arr[i]+curNum;        else curNum = arr[i];        if(curNum > max)            max = curNum;    }    cout<<max;}int main(){    f();    return 0;}
[解决办法]
LZ要多赏点给我哦。。。虽然我后来的但是确实给了解释和自写的代码哦
[解决办法]
看看 Programming Pearl 吧， O(n) 算法。一次遍历就行了。
可用 prefix-sum 解释， 非常直观。
而且求所有局部最大子串的算法也是 O(n). 

 

查看更多 下一篇