最大子段和分治法 C++分治法求最大子段和问题 - 奇闻 - 52资讯网
首页 > 奇闻 > 正文

最大子段和分治法 C++分治法求最大子段和问题

用分治法求最大子段和的值可以求出来
但是在求最大子段的下标时出了问题

我是定两个全局变量index1=0,index2=0来表示最大子段的下标。
但是输出结果index1,index2的值总是0   似乎在代码中不能对index1,index2进行赋值。
求大牛帮忙解惑!!万分感谢

#include <iostream>
#include<time.h>
using namespace std;

int index1 = 0;
int index2 = 0;
int maxSum(int a[], int left, int right) {  //求序列啊[left]到a[right]的最大子段
int sum = 0, midSum = 0, leftSum = 0, rightSum = 0;
int center, s1, s2, lefts, rights,j,i;
if (left == right)
sum = a[left];
else {
center = (left + right) / 2;  // 划分
leftSum = maxSum(a, left, center);//对应情况1 递归求解
rightSum = maxSum(a, center + 1, right);//对应情况2.递归求解
s1 = 0; lefts = 0;
for (  i = center; i >= left; i--) {//对应情况三
lefts += a[i];
if (lefts > s1)
s1 = lefts;
}
s2 = 0, rights = 0;
for ( j = center + 1; j <= right; j++) {
rights += a[j];
if (rights > s2)
s2 = rights;
}
midSum = s1 + s2;                    
if (midSum < leftSum &&leftSum>rightSum){//比较出最大子段,求出最大子段下标index1,index2
sum = leftSum;
index1 = left;    
index2 = center;
}
if(midSum > leftSum && midSum>rightSum){
sum = midSum;
index1 = i+1;
index2 = j-1;
}
else{
sum = rightSum;
index1 = center + 1;
index2 = j+1;
}

}
return sum;
}

int main(){

int a1[] = {-1,1,1,1,1};

cout<<"最大子串值为:"<<maxSum(a1,0,4)<<endl<<"下标为"<<index1<<"到"<<index2<<endl;

}

小编推荐
  • 在神农架发现的野人的头发是什么 中国神龙架
      世界上有许多关于野人的传说,比较著名的留下过影像资料的有美国的大脚怪,中国神龙架的野人,喜马拉雅的雪人,还有高加索到蒙古一带的阿尔玛斯人等等。 而其中尤其是我国神农架野人,其

    2019-06-28

  • 河南回乱真实 真实的历史——死亡2000万人的
    附一位回族读者的留言:忍者_a737: @晓明73 在那个战乱社会无故的是人民老百姓,我听我爷爷说我们老家是陕西省渭南市的回族,那个社会回族就不敢承认自己是回族,如果说自己是回族就把你全家

    2019-06-28

  • 世界上最长的人牙 18岁的男孩拔出了世界最长
      在这个注重美观的年代,很多人都注重自己的五官,牙齿也是大家保养的对象,大家都会尽量让自己的牙齿变得整齐白皙,但是有一个少年不按照常理出牌,少年长出了世界上最长的牙齿,为此还会

    2019-06-28

  • 世界上最最大的鱼 鲸鲨身体长度达到20米
    世界上最大的鱼是一种叫做鲸鲨的鱼,他们最长可以达到20米。不过可不要认为这是一种鲨鱼,事实上这是一种鱼类。它们在海洋之中的地位也是超然的,并没有什么天敌,不过如今的鲸鲨树木已经非常

    2019-06-28

  • 世界上最大的乌龟玄武 我的世界玄武雕像展示
      我的世界玄武雕像展示 好大的一只龟啊。玄武是中国的四大神兽之一,是重力的代言,那下面的这个在我的世界里面的玄武就是非常的另类了哦~虽然外表和玄武一样的,但是他不在是单一的颜色了

    2019-06-28

热图推荐