一个算法，求最大值

一个无序的数组，比如1000个数，
在里面找到连续的数列，使其和最大
比如-1-1-1-11111111,最大的就是1111111.
谢谢大家

22 个解决方案

#1

去网上搜索“最大连续子段和”

#2

前两天大家好像刚刚讨论过，我就引用一下别人的方法吧！

假设序列为

m1,m2,m3,m4.....mn

求加和

s1 = m1
s2 = m1 + m2
s3 = m1 + m2 + m3
......
sn = m1 + m2 + m3 + ...... + mn

找出s1到sn中的最小值sj及最大值sk

当k >= j时,j到k就是最大序列
当k < j时,k到j就是最小序列

#3

当k >= j时,j到k就是最大序列
当k < j时,k到j就是最小序列
这两句是什么意思呢。当k<j时的最大序列怎么求啊。

#4

public static int MaxSum(int a[]){
int Max = 0;
int temp = 0;
for(int i = 0 ;i < a.length;i++){
if(temp<0){
temp = 0;
}else{
temp = temp+a[i];
if(Max <temp){
Max = temp;
}

}
}
return Max;
}

#5

4楼的。如果我的数组都是小于0的数，怎么办呢。-1，-1，。。。。
你的算法只能是0

#6

是有这个问题，小修改了一下，感觉写的不太好。
public static int MaxSum(int a[]){
int Max_1= 0;
int temp = 0;
int count =0;
int Max_2 = a[0];
for(int i = 0 ;i < a.length;i++){
if(temp<0){
if(Max_2 < temp){
Max_2 = temp;
}
temp = 0;
}else{
temp = temp+a[i];
if(Max_1 <temp){
Max_1= temp;
count++;  //防止出现 -1，1的情况
}

}
}
return count>0?Max_1:Max_2;
}

#7

很感谢你的热情，但是很遗憾，你的算法还有问题。下面是正确的算法。
int[] a = new int[] { -1, -9, -7, 34, -9, -8, -45, 3, 4, -1, -5, 3, 4, -6, -7, -9 };
对这个数组调用，应该最大值为34。

int submax1(int[]a )
        {            
            int b = 0;
            int bn = -32767;          
            int sum = 0;
            for (int i = 0; i < a.Length; i++)
            {
                if (b > 0)
                {
                    b += a[i];
                }
                else if (a[i] > bn && a[i] < 0)
                {
                    bn = a[i];
                    b = a[i];
                }
                else
                {
                    b = a[i];
                }
                if (b > sum)
                {
                    sum = b;
                }
                Console.WriteLine("a[i]={0}   b={1}   bn={2}  sum={3}", a[i], b, bn, sum);
            }
            if (sum == 0)
                return bn;
            else
                return sum;
        }

#8

学了。

#9

我再帮你扩展一下

找和最大的，长度最小的。。。。。

int MaxSum(int *A,int length)
{
int sum=A[0];                         //最大和
int temp=A[0];
int p=0;int q=0;                      //最大和第一个下标和最后一个下标
int pt=0;int qt=0;
for(int i=1;i<=length-1;++i)
{
if(temp<0)
{
temp=0;
pt=i;
qt=i;
}
temp+=A[i];
qt=i;
if(temp>sum)
{
p=pt;
q=qt;
sum=temp;
}
if(temp==sum&&qt-pt<q-p)
{
p=pt;
q=qt;
}
}
for(int i=p;i<=q;++i)
{
cout<<A[i]<<" ";
}
cout<<endl;
return sum;
}

找到最大和的数值串，如果有多个最大数值串，取长度最小的

#10

int MaxSum(int *A,int length)
{
	int sum=A[0];
	int temp=A[0];
	int p=0;int q=0;
	int pt=0;int qt=0;
	for(int i=1;i<=length-1;++i)
	{
		if(temp<0)
		{
			temp=0;
			pt=i;
			qt=i;
		}
		temp+=A[i];
		qt=i;
		if(temp>sum)
		{
			p=pt;
			q=qt;
			sum=temp;
		}
		if(temp==sum&&qt-pt<q-p)
		{
			p=pt;
			q=qt;
		}
	}
	for(int i=p;i<=q;++i)
	{
		cout<<A[i]<<" ";
	}
	cout<<endl;
	return sum;
}

改个格式

#11

DP

#12

这个。。。。。

是要求出和最大么

#13

//我的程序改过来了，逻辑错了。
public class Max {

public static int MaxSum(int a[]){
int Max_1 = 0;
int temp = 0;
int Max_2 = a[0];
for(int i = 0 ;i < a.length;i++){
if(temp<0){
if(Max_2 < temp){
Max_2 = temp;
}
temp = 0;
}  
temp += a[i];
if(Max_1 < temp){
Max_1 = temp;
}
}
return Max_1>0?Max_1:Max_2;
}

public static void main(String[] args) {
int a[] = new int[]{-1, -9, -7, 34, -9, -8, -45, 3, 4, -1, -5, 3, 4, -6, -7, -9};
System.out.println(Max.MaxSum(a));

}
}

#14

Programming Pearls 上有 O(n) 的算法

#15

如果把一唯的改成2唯的求最大子矩阵应该怎么求呢

#16

int MaxSum(int a[] , int length)
{ 
    int i;
    int saveSum = 0x80000000;  ////与机器int定义有关
    int curSum =a[0];
    for(i=0 ;i < length ;i++)
    { 
        if(a[i] <0)   //小于0  －－ 1 保存最大和 ，2 新的计数和开始
        { 
            if(saveSum < curSum)   //如果以前和比当前小 ，交换
            { 
                saveSum = curSum; 
            } 
            curSum = 0;           //重新开始计数
        }else
        { 
            curSum = curSum+a[i]; //和累加 
        } 
    } 
    
    return saveSum ;
}

#17

to nandizhu
你的程序貌似有问题
int a[] = { -1, -9, -7, 34, -9, -25, 45, 3, 4, -1, -5, 3, 4, -6, -7, -9 };
你的输出是 34 -9 -25 45 3 4 -1 -5 3 4
正确的输出是 45 3 4 -1 -5 3 4

#18

to nandizhu
你把temp<0改成temp<=0,貌似就对了
if(temp<=0) 
{ 
temp=0; 
pt=i; 
qt=i; 
}

#19

学习

#20

可以把它存到SQL SERVER中,然后,使用

select max(n) from xxx

来做,也应该没问题吧..

#21

#include "stdafx.h"
#include <stdio.h>

int Maxsub(const int *array, int Num)
{
	int MaxEnd = 0;
	int IntMax = 0;
	for (int i=0; i<Num; i++)
	{
		MaxEnd = ((MaxEnd+array[i]) > 0 ? MaxEnd+array[i]:0);
		IntMax = (MaxEnd > IntMax ? MaxEnd:IntMax);
	}
	return IntMax;
}

int main(int argc, char* argv[])
{
	int a[] = {34, -41, 59, 26, -53, 58, 97, -93, -23, 84};
	printf("%d\n",Maxsub(a, 10));
	return 0;
}

#22

学习 and  接分