求一个整数数组中最大子数组的和

要求： 输入一个整形数组，数组里有正数也有负数。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为O(n)

思路比较简单，主要就是怎么去找这个最大

设置两个常量：最大值max和累加值tmp都初始化为数组第一个元素的值

判断tmp，如果tmp<0，tmp赋值为0，tmp+=a[i]，直至循环结束

其实就是通过首元素值(tmp)是否小于0，小于的话赋值0累加上其后继元素，判断max与tmp大小，并将大的值重新赋值给max。

循环上一步骤

例子：-1 2 -3 4 5 很容易得到这个数组的最大子数组和为9，通过我的思路，初始化tmp=a[0]=-1;

tmp<0，tmp=0，加上其后继元素tmp+2=2，tmp>0，加上其后继元素tmp+(-3)=-1<0，赋值为0，循环这个过程，不难得到结果9...

 1 package test1;
 2 
 3 import java.util.Scanner;
 4 
 5 public class test1 {
 6     public static  int maxSum(int[] array){//得到最大子数组和
 7         if(null == array || array.length == 0){
 8             return 0;
 9         }
10         int tmp = array[0];
11         int max = array[0];
12         for(int i = 1; i < array.length; i++){
13             if(tmp < 0){
14                 tmp = 0;
15             } 
16             tmp += array[i];  
17             max = Math.max(max, tmp); 
18         }
19         return max;
20     }
21     static int[] generateRandomArr(int n,int min, int max) {//产生随机数组，参数n是大小，后面的是范围min-max
22         int [] a = new int [n];
23         for (int i = 0; i < n; i++) {
24             int random = (int) Math.floor(Math.random() * (max - min + 1) + min);
25             a[i]=random;
26         }
27         return a;
28     }
29     public static void main(String[] args) {
30         
31         int [] a = generateRandomArr(5,-5,5);
32         System.out.println("数组的大小："+a.length+" ");
33         Scanner in=new Scanner(System.in);
34         /*int []a = new int[4];
35         for(int i=0;i<4;i++)
36         {
37             a[i]=in.nextInt();
38         }*///测试所用
39         System.out.print("数组元素：");
40         for(int i = 0;i < a.length; i++)
41         {
42             System.out.print(a[i]+" ");
43             if(i==a.length-1)
44             {
45                 System.out.println();
46             }
47         }    
48         System.out.println("数组子数组的最大和："+maxSum(a));
49         
50     }
51 }

Java Code

第二种类型：数组不是平时的一维数组，而是环形数组。

解题思路，环形数组的最大子数组要不就是再a[0]-a[n]，要不就在a[n]-a[n-1](注意是循环过去的)段里

所以我们反过来想，可以在a[0]-a[n]中找一个子数组最小和，并定位其末尾元素位置，再从此位置对数组进行普通数组的那样的运算

得到的就是子数组的最大和，代码如下

#include<iostream>
#include<cstring>
using namespace std;
int n;
int NotCircle(int a[])
{
    int maxn=-1000,sum[10000];
    sum[0]=a[0];
    for(int i=1;i<n;i++)
    {
        if(a[i]<a[i]+sum[i-1])
        {
            sum[i]=a[i]+sum[i-1];
        }
        else
        {
            sum[i]=a[i];
        }
        if(maxn<sum[i])
            maxn=sum[i];
    }
    return maxn;
}

int findmin(int a[])
{
    int minx=10000000;
    int sum[10000],flag=0;
    sum[0]=a[0];
    for(int i=1;i<n;i++)
    {
        if(sum[i-1]<0)
            sum[i]=sum[i-1]+a[i];
        else
            sum[i]=a[i];
        if(minx>sum[i])
        {
            minx=sum[i];
            flag=i;
        }
    }
    return flag;
}

int Circle(int a[])
{
      int minid=findmin(a),j,sum=0;
      int key=(minid+1)%n;
      int maxn=a[key];
      for(j=key;(j%n)!=minid;j++)
      {
          if(sum>0)
            sum+=a[j%n];
        else
            sum=a[j%n];

          if(maxn<sum)
            maxn=sum;
      }
      return maxn;
}

int main()
{
    int a[100],i,j;
    cout<<"输入数组元素个数"<<endl;
    cin>>n;
    cout<<"输入数组各元素的值"<<endl;
    for(i=0;i<n;i++)
        cin>>a[i];
    int max1=NotCircle(a);
    int max2=Circle(a);
    int max3=max(max1,max2);
    cout<<"环形数组的最大子数组和为:"<<max3<<endl;
    return 0;
}

C++ Code

最后比较这两种解法哪个值最大，那么他就是环状数组最大连续子数组的和

THE END