求子数组的最大和-蒲公英云

求子数组的最大和

- 日理万妓 2022-08-02 01:18 249阅读 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  
------------------------------------------------------------