返回一个整数数组中最大子数组的和（有环）

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。源程序代码

 1 //返回一个一维整数数组最大子数组和最大值（有环）
 2 package ketang;
 3 import java.util.*;
 4 public class SumArray {
 5     public static void main(String[] args) {
 6         Scanner sca=new Scanner(System.in);
 7         System.out.println("输入整数数组数的个数");
 8         int num=sca.nextInt();
 9         int a[],b[];
10         a=new int[num];
11         b=new int[num];
12         System.out.println("输入数组的数");
13         int i;
14         for(i=0;i<num;i++)
15         {
16             a[i]=sca.nextInt();
17         }
18         int t,j=0,sum=0,max=a[0];
19         for(i=0;i<num;i++)  //未成环之前找最大值
20         {
21             sum+=a[i];
22             if(max<sum)
23             {
24                 max=sum;
25             }
26             if(sum<0)
27             {
28                 sum=0;
29             }
30         }
31         /* 实现首尾相接  */
32         int min=a[0];
33         for(i=0;i<num;i++) //找到最小值
34         {
35             if(min>a[i])
36             {
37                 min=a[i];
38                 j=i;
39             }
40         }
41         t=j;    //将最小值下标j值赋给t
42         i=0;
43         while(j<num)
44         {
45             b[i]=a[j];
46             i++;
47             j++;
48         }
49         j=0;
50         while(j<t)
51         {
52             b[i]=a[j];
53             i++;
54             j++;
55         }
56         sum=0; //接着初始化sum为0
57         for(i=0;i<num;i++)  //连成环之后找最大值
58         {
59             sum+=b[i];
60             if(max<sum)
61             {
62                 max=sum;
63             }
64             if(sum<0)
65             {
66                 sum=0;
67             }
68         }
69         System.out.println("最大子数组和为 "+max);
70     }
71 }

The Main Code

3.结果截图

4.编程总结

　　此次编程只需在原来程序基础上进行改进即可，难点在于如何找到连成环的关键位置，关键位置找到后形成一个新数组，再利用上次的思想进行寻找最大值即可。

5.psp

爱程序网

Tags：[db:关键字]