数组2

题目:

返回一个整数数组中最大子数组的和。

要求：要求程序必须能处理1000 个元素；

每个元素是int32 类型的；

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

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

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

首先向王老师道个歉，晚了这么久才发微博。

1. 设计思想

设计思想大致与”数组“（上一篇博客）无区别，只是做了小范围更改。首先是用random产生随机数，可以产生政府混合，怎么求最大子数组，重点是2个思想：①在这个循环中，把前几个相加，看是否是正数。② 其次看（i+1）的和是否大于（i）的和。

根据这就可以用一个循环来进行计算。接下来就是考虑其他的问题，比如最大子数组的起始位置和最终位置。把这个加入到for循环中，用if条件语句进行判断。最后输出即可。

2. 出现问题以及解决方案

出现的问题就是数溢出，本来的想法是用递归调用，来调整输入的数，但是一直有bug，所以就采用了直接判断的方法。在主函数中直接用if条件语句。

3. 源代码

import java.util.Random;
import java.util.Scanner;


public class main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int a[]=new int[1000000];
        int sum,d,temp1=0,temp2=0,flag1=0,flag2=0;  //分别记录子数列的起始和结束位置
        System.out.print("请输入数组元素的个数： ");
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        if(m>999999)
        {
            System.out.print("请重新输入数组元素的个数： ");
            m=sc.nextInt();
        }
        Random rand = new Random();
        for(int i=0;i<m;i++)//循环为数组赋值
        {
            a[i] = rand.nextInt(40)-20;
            System.out.print(a[i]+" ");
        }
        sum=a[0];
        d=sum;
        for(int i=0;i<m;i++)//核心循环，来判断怎么产生最大子数组
        {
            if(d<=0){
                d=0;
                temp1=i+1;
                temp2=i;
            }        
            d+=a[i+1];
            temp2++;
            if(d>sum){
                sum=d;
                flag1=temp1;
                flag2=temp2;
            }
        }
        System.out.println("");
        System.out.print("子数组的组成元素为：    ");
        for(int i=flag1;i<=flag2;i++)
            System.out.print(a[i]+" ");
        System.out.println("");
        System.out.println("子数组和的最大值为：    "+sum);

    }

}

4. 截图

以下是运行1000个数组元素的截图：

5. 总结

通过这次的程序，我认识到了自己的不足。首先就是对递归函数的运用，一定要攻克这个难题。其次就是对数据溢出的考虑。查了查资料，这属于bug的方面，以后再学习中一定要考虑到这个问题。

6. 小组照片