输入一个有正负整数的数组，寻找最大子数组

素颜马尾好姑娘i 2022-06-07 12:39 164阅读 0赞

给定一个整型数组，里面的元素有正有负，数组中连续的一个或者多个整数构成一个子数组。求所有子数组中元素和的值最大的子数组。

分析思路:  需要2个变量来标记已经记录下的当前最大子数组的起始位置start0和末尾位置end0

需要2个变量来标记正在寻找的子数组的起始位置start1和末尾位置end1

需要两个子数组和值记录sum0，sum1

1、先将整个数组作为最大子数组，并求sum0

2、从数组的起始位置开始标记start1=end1=0；sum1=array\[start1\]

3、sum1比0大，说明start1有可能作为最大子数组的起始位置,同理end1有可能作为最大子数组的末尾位置

sum1比0小，说明start1不可能作为最大子数组的起始位置，start1++；end1=start1; sum1=array\[start\];

sum1比sum0大，更新最大子数组的起始和末尾位置  start0=start1;end0=end1;sum0=sum1;

4、循环遍历整个数组

#include
       
        
    #include 
        
          
    using namespace std; 
    /*
    一个数组，从数组的起始位置开始，如果大于0，说明可以继续往后逐个添加作为子数组的拓展，如果寻找过程中最大子数组的总和小于0
    ，说明碰到一个迫使总和降到0以下的数，这个时候应该往后重新标定寻找最大子数组的开始下标和末尾下标，继续往后找。
    */
    int main() { 
    	int a[] = {3,2,-6,4,7,-3,5,-2};//数组
    	int N = sizeof(a) / sizeof(int);//数组长度
    	int start0 = 0;//最大子数组起始下标
    	int end0 = N - 1;//最大子数组
    	int sum0=0;//最大子数组总和
    	int start1 = 0;//寻找最大子数组起始下标
    	int end1 = start1;//寻找最大子数组末尾下标
    	int sum1=start1;//寻找最大子数组总和
         //先将整个数组作为最大子数组，求和
    	for (int i = 0; i < N; i++)
    	{
    		sum0 += a[i];
    	}
    	//一次遍历
    	for(int i=0;i
         
           sum0)
    		{
    			start0 = start1;
    			end0 = end1;
    			sum0 = sum1;
    			continue;
    		}
    		else if(sum1<0) //sum1小于0，说明前面那个子数组到这个当前的数往后是不能再加了，start1要往后移end1也要往后面移
    		{
    			start1++;
    			end1 = start1;
    			sum1 =a[start1];
    			continue;
    		}
    		else if(sum1>0)//sum1>0,end1要往后移
    		{
    			end1++;
    			sum1 +=a[end1];
    		}
    	}
    	//最后start0是记录最大子数组的起始下标，end0记录的是最大子数组的末尾下标，sum0是记录最大子数组的总和
    	for (int i = start0; i <= end0; i++)
    		cout << a[i] << " ";
    	cout << endl;
    	cout << "子数组下标起始：" << start0 << ";子数组下标结尾：" << end0 << endl;
    	cout <<"最大子数组总和："<< sum0 << endl;
    	return 0;
    }