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

1.设计思想　　

　　（1）首先创建一个一维数组a[]，根据用户输入的数组长度及数组内容进行存储数据。

　　（2）再定义几个变量，sum用于求和，max为和最大值，num为数组长度。

　　（3）开始for循环，sum初始化为0，max初始化为a[0]。循环内容为sum+=a[i]；如果sum比max大则将sum值赋给max，如果sum小于0，则定义sum=0。直至循环结束，得到最大子数组的和。

　　（4）寻找a数组最小值，得到其下标j，将j值赋给t。创建数组b，进行两次循环，第一次循环i=0,每循环一次j值就增加1，b[i]=a[j]，当j>=num时，第一次循环结束。进行第二次循环，令sum=0，j=0。每循环一次j值就增加1，b[i]=a[j]，当j>=t时，循环结束，便成环。

　　（5）开始for循环，sum初始化为0，max为未成环之前得到的最大值。循环内容为sum+=b[i]；如果sum比max大则将sum值赋给max，如果sum小于0，则定义sum=0。直至循环结束，得到最大子数组的和。

2。源程序代码

package shuzu;
import java.util.*;
public class DongTai {
    public static void main(String[] args) {
        Scanner sca=new Scanner(System.in);
        System.out.println("输入整数数组数的个数");
        int num=sca.nextInt();
        int a[],b[];
        a=new int[num];
        b=new int[num];
        System.out.println("输入数组的数");
        int i;
        for(i=0;i<num;i++)
        {
            a[i]=sca.nextInt();
        }
        int t,j=0,sum=0,max=a[0];
        for(i=0;i<num;i++)  //未成环之前找最大值
        {
            sum+=a[i];
            if(max<sum)
            {
                max=sum;
                
            }
            if(sum<0)
            {
                sum=0;
            }
        }
        /* 实现首尾相接  */
        int min=a[0];
        for(i=0;i<num;i++) //找到最小值
        {
            if(min>a[i])
            {
                min=a[i];
                j=i;
            }
        }
        t=j;    //将最小值下标j值赋给t
        i=0;
        while(j<num)
        {
            b[i]=a[j];
            i++;
            j++;
        }
        j=0;
        while(j<t)
        {
            b[i]=a[j];
            i++;
            j++;
        }
        sum=0; //接着初始化sum为0
        for(i=0;i<num;i++)  //连成环之后找最大值
        {
            sum+=b[i];
            if(max<sum)
            {
                max=sum;
            }
            if(sum<0)
            {
                sum=0;
            }
        }
        System.out.println("最大子数组和为 "+max);
    }
}

View Code

实验截图

1正数

2负数

3正负

设计思路：（副）

2.1：建立一个可以自己在外部输入数组长度的2维数组，

2.2：如果输入的初始数组长度为X的话那就定义数组的长度为X的累乘；

2.3：如何把数组形成一个环状数的存放方式如下表

下标	0	1	2	3	4	5
shuzu[][0]	1	-1	3	-1	3	3
shuzu[][]	1	1	4	-1	3	3

实验代码：

package shuzu;
import java.util.Scanner;

public class DongTai01 {
    public static void main(String args[])
    {
         
        Scanner num = new Scanner(System.in);
        System.out.println("请输入数组的长度");
        int a = num.nextInt();
        int shu = a;
        int[][] shuzu = new int[shu][2];
        Scanner sca = new Scanner(System.in);
        System.out.println("请输入" + shu + 
                "以内个整数");
        for(int i = 0;i < shu-1;i++)
        {
           
            

            shuzu[i][0] = sca.nextInt();
            System.out.println("你已经输入" + (i +1) + "个数" + "，还有"+(shu -i -1)+"个数");
            if(i == shu-2)
                
            {
                
                break;
               
            }
            
        }
       shuzu[shu-1][0] = shuzu[0][0];
        for(int z = 0;z <shu;z++)
        {
             System.out.println(shuzu[z][0]
                     );
        }
        shuzu[0][1]=shuzu[0][0];
        for(int  i = 1;i < shu;i++)
        {
            if(shuzu[i-1][1]<0)
            {
                shuzu[i][1]=shuzu[i][0];
            }
            if(shuzu[i-1][1]>=0)
            {
               shuzu[i][1] = shuzu[i-1][1]+shuzu[i][0];
            }
        }
        int max=shuzu[0][1];
       for(int i=0;i<shu;i++)
        /*{
         
            if(shuzu[i][1]>=max) 
            {
                
                max=shuzu[i][1];
            }
        }
        */
            // System.out.println("最大和为"+max);
        System.out.println("各个子数组最大"+shuzu[i][1]);
        
    }

}

View Code