求数组的字数组之和的最大值

思路:给定一个数组A, 找其中和最大的子串,可以可以从A[0]开始,往后累加和放在start中,如果start<0,将可以抛弃当前元素值,不再进行累加,maxSum保存最大的子串和。。并从下一个位置重复上述过程。

/*******************************************
   Author        : Jun Zhang
   Email         : ewalker.zj@gmail.com
   Last Modified : 2015-08-02 14:08
   Filename      : subMax.cpp
   Description   :
*******************************************/
#include<iostream>
int subMax(int *data, int n)
{
   	int start = data[0];           // record the current sum, >0
   	int maxSum = data[0];          // the maxSum
   	for(int i = 1; i < n; i++)
   	{
      		if(start < 0)             // preSum < 0
         			start = 0;            // new start position
      		start += data[i];
      		if(start > maxSum)
         			maxSum = start;
   	}
   	return maxSum;
}
int main()
{
   	int buf[10] = {2, -4, 5, 6, 2, -3, 8, 1, -12, -3};
   	std::cout<<subMax(buf, 10)<<std::endl;
   	return 0;
}

时间复杂度O(n),空间复杂度O(1)
3种变形:
1、求字数组和的绝对值的最大值
2、返回最大字数组位置
 

//需返回最大字数组的位置
struct outInfo
{
   	int begin;
   	int end;
   	int sum;
   	struct outInfo *next;
};
int subMax1(int *data, int n)
{
   	int start data[0];
   	int maxSum = data[0];
   	int pos;
   	int begin = 0, end;
   	int new;
   	outInfo *p, *info, *head;
   	head = (outInfo*)malloc(sizeof(outInfo));
   	p = head;
   	int ret = 0;
   for(int i = 1; i < n; i++)
   	{
     		if(start < 0)
     		{
       			if(ret == 0){
       				start = 0;
				       //此处可以保存当前字数组信息
       				ret = -1;
       				if(maxSum > p->sum)          // 子数组和大于当前存储值,覆盖
       				{
					          p->begin = begin;
          					p->end = end;
          					p->sum = maxSum;
       				}
       				else if(maxSum == p->sum)    // 相同的子数组和
       				{
          					info = (outInfo*)malloc(sizeof(outInfo));
          					info->begin = begin;
          					info->end = end;
          					info->sum = maxSum;
          					info->next = NULL;
          					p->next = info;
          					p = p->next;
       				}
     			}
   		}
  		if((ret == -1))&&(data[i] > 0))
  		{
			     begin = i;                // new begin;
			     ret = 0;
  		}
		  start += data[i];
  		if(start > maxSum)
  		{
     			maxSum = start;
     			end = i;
  		}
	}
  	if(ret == 0)
  	{
     		if(maxSum > p->sum)
     		{
        			p->begin = begin;
        			p->end = end;
        			p->sum = maxSum;
     		}
		     else if(maxSum == p->sum)
     		{
        			info =(outInfo*)malloc(sizeof(outInfo));
        			info->begin = begin;
        			info->end = end;
        			info->sum = maxSum;
        			info->next = NULL;
        			p = p->next;
     		}
   	}
	return maxSum;
}

 
3、数组收尾相连

Leave a Reply

Your email address will not be published. Required fields are marked *