4月25日课上练习一维数组最大子数组（debug版）

一维数组中求最大子数组的算法

package com.wangwang.mar;

import java.util.Scanner;
public class Sum {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner sc=new Scanner(System.in);
        System.out.println("输入数组长度");
        int n=sc.nextInt();
        System.out.println("输入数组数据（用空格分开）");
        int i;
        int a[]=new int[n];
        for(i=0;i<n;i++)
            a[i]=sc.nextInt();
         
        int begin=0;//子数组开始下标
        int end=0;//子数组结束下标
        int maxValue=a[0];
        int tempValue=maxValue;
         
         
        //for循环寻找最大和的连续子数组
        for(i=1;i<n;i++)
        {
            tempValue+=a[i];
            
            if((tempValue>a[i])&&(tempValue>maxValue))
            {
                end=i;
                maxValue=tempValue;
                
            }
             
            else if(tempValue<=a[i])
            {
                begin=i;
                end=i;
                tempValue=a[i];
                
            }
        }
         
         
        //输出最大和的连续子数组的相关信息
        System.out.println("最大子数组和为："+maxValue+"
子数组内容为：");
        System.out.println("下标：");
        for(i=begin;i<=end;i++)
            System.out.print(i+"  ");
        System.out.println("
"+"下标对应数值：");
        for(i=begin;i<=end;i++)
            System.out.print(a[i]+"  ");
         
         
    }
 
}

　加入debug后，修改部分代码，如下：

 1 package com.wangwang.mar;
 2 
 3 import java.util.Scanner;
 4 public class Sum {
 5  
 6     public static void main(String[] args) {
 7         // TODO Auto-generated method stub
 8  
 9         Scanner sc=new Scanner(System.in);
10         System.out.println("输入数组长度");
11         int n=sc.nextInt();
12         System.out.println("输入数组数据（用空格分开）");
13         int i;
14         int a[]=new int[n];
15         for(i=0;i<n;i++)
16             a[i]=sc.nextInt();
17          
18         int begin=0;//子数组开始下标
19         int end=0;//子数组结束下标
20         int maxValue=a[0];
21         int tempValue=maxValue;
22          
23         System.out.println("设定起始数组为a[0]");
24         //for循环寻找最大和的连续子数组
25         for(i=1;i<n;i++)
26         {
27             tempValue+=a[i];
28             System.out.print("将a["+i+"]加入起始数组进行运算");
29             if(tempValue>a[i])
30             {
31                 if(tempValue>maxValue) {
32                 end=i;
33                 maxValue=tempValue;
34                 System.out.println(" "+"最大值更新，当前最大值为："+maxValue);
35                 }
36                 else {
37                     System.out.println(" "+"构成的新数组最大值不变为："+maxValue);    
38                 }
39             }
40              
41             else if(tempValue<=a[i])
42             {
43                 begin=i;
44                 end=i;
45                 tempValue=a[i];
46                 maxValue=tempValue;
47                 System.out.println(" "+"数组总和<该元素，该元素作为当前最大值为："+maxValue);
48             }
49         }
50          
51          
52         //输出最大和的连续子数组的相关信息
53         System.out.println("最大子数组和为："+maxValue+"
该子数组内容为：");
54         System.out.println("下标：");
55         for(i=begin;i<=end;i++)
56             System.out.print(i+"  ");
57         System.out.println("
"+"下标对应数值：");
58         for(i=begin;i<=end;i++)
59             System.out.print(a[i]+"  ");
60          
61          
62     }
63  
64 }

运行结果，如图：

4月25日课上练习 一维数组最大子数组（debug版）

4月25日课上练习一维数组最大子数组（debug版）