求子数组的最大和

- 日理万妓 2022-08-02 01:18 161阅读 0赞

题目：   
输入一个整形数组，数组里有正数也有负数。   
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。   
求所有子数组的和的最大值。要求时间复杂度为O(n)。   
   
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，

因此输出为该子数组的和18。

// maxofsubarray.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<vector>
    #include<iostream>
    using namespace std;
    int maxofsubarray(int*in, int len, int startpos);
    int sumofvec(vector<int>vec);
    int maxofvec(vector<int>vec);
    int endpos = 0;
    int _tmain(int argc, _TCHAR* argv[])
    {
    	const int len = 8;
    	int a[len] = { 1, -2, 3, 10, -4, 7, 2, -5 };
    	int ss = 0;
    	
    	int max = 0;
    	while (ss < len)
    	{
    		//endpos=0;
    		int mm=maxofsubarray(a, len, ss);
    		if (mm > max)
    			max = mm;
    		if (endpos == 0)
    			ss = ss + 1;
    		else
    			ss = endpos + 1;
    		cout << endpos << endl;
    	}
    
    	cout << max << endl;
    	system("pause");
    	return 0;
    }
    
    int maxofsubarray(int*in, int len,int startpos)
    {
    	
    	vector<int>aa,bb;
    	while (in[startpos] <= 0)
    	{
    		++startpos;
    		if (startpos >= len)
    			return -1;
    	}
    	bb.push_back(in[startpos]);
    	int max = in[startpos];
    
    	for (int i = startpos+1; i < len; i++)
    	{
    		if (i == len - 1)
    			endpos = 0;
    		if (in[i]>=0)
    		bb.push_back(in[i]);
    		if (in[i] < 0)
    		{
    			int v = sumofvec(bb);
    			aa.push_back(v);
    			if (in[i] + v >= 0)
    			{
    				bb.push_back(in[i]);
    				continue;
    			}
    			else
    			{
    				endpos = i;
    				break;
    			}
    		}
    		
    		
    	}
    	
    	return maxofvec(aa);
    }
    
    int sumofvec(vector<int>vec)
    {
    	vector<int>::iterator it;
    	int sum = 0;
    	for (it = vec.begin(); it != vec.end(); it++)
    		sum += *it;
    	return sum;
    }
    
    int maxofvec(vector<int>vec)
    {
    	vector<int>::iterator it;
    	int max = 0;
    	for (it = vec.begin(); it != vec.end(); it++)
    		if(*it>max)
    			max=*it;
    	return max;
    
    
    }

简洁的解法

int main()  
    {  
        int a[10]={1,-8,6,3,-1,5,7,-2,0,1};  
        cout<<maxSum(a,10)<<endl;  
        return 0;  
    }  
      
    
       
    int maxSum(int* a, int n)  
    {  
      int sum=0;  
      int b=0;  
      
      for(int i=0; i<n; i++)  
      {  
        if(b<=0)           //此处修正下，把b<0改为 b<=0  
          b=a[i];  
        else  
          b+=a[i];  
        if(sum<b)  
          sum=b;  
      }  
      return sum;  
    }  
    运行结果，如下：  
    20  
    Press any key to continue  
    ------------------------------------------------------------