求數組中的最小子數組，時間復雜度o(n)，java

?

石家莊鐵道大學    信1405-1 班   唐炳輝

?

題目：給定一個整數數組，找到一個具有最小和的子數組。返回其最小和。

?

?

設計思路：兩個變量 ，一個記錄當前并入的數組的值，另外一個記錄所算過得最大的數組的值,當并入的值為小于零的時候，就沒必要進行繼續的相加了，因為再加也不可能比后邊單獨的數字大，所以，為負數就重新刷新位置，重置子數組的長度重新去找一個新的子數組

?

//石家莊鐵道大學    信1405-1 班   唐炳輝：三藏
/**給定一個數組，求出這個數組中子數組的最大值，求出，要求時間復雜度為O(n)**/
 package java_ketang;
import java.util.Scanner;


 
public class MinArray {



public static void main(String[] args) {
    MinArray f = new MinArray();
        
    //用戶自己定義數組的長度并 自行輸入一串數組
        
        Scanner in=new Scanner(System.in);
        System.out.print("請輸入數組長度：");
        int flase0g=in.nextInt();
        //輸入數組中的各個數值
        System.out.print("請依次輸入整數：");
        int Arr[]=new int[flase0g];
        for(int i=0;i<flase0g;i++)
        {
            Arr[i]=in.nextInt();
        } 
        //輸出用戶輸入的數組  
        System.out.print("您輸入的數組為 ");
        for(int i=0;i<flase0g;i++)
        {
            System.out.print(Arr[i]+"  ")  ;
        }  
        
        //輸出最后的結果
        f.findMaxArr(Arr);
    }

    public void findMaxArr(int[] arr) {
        int Arr = 0;//用來記錄當前并入的數組的和
        int MaxArr = 0;//用來記錄之前的最大的數組和
        int A = arr.length;
        int Location1=0;
        int Location2=0;//用來記錄子數組的最后一個位置
        
        int i;
        

    /**核心算法，兩個變量 ，一個記錄當前并入的數組的值，另外一個記錄所算過得最大的數組的值
        當并入的值為小于零的時候，就沒必要進行繼續的相加了，因為再加也不可能比后邊單獨
        的數字大，所以，為負數就重新刷新位置，重置子數組的長度重新去找一個新的子數組**/
        for ( i = 0; i < A; i++) {
            Arr += arr[i];
            if (Arr < 0) {
                Arr = 0;
                
                
                }
            if (Arr > MaxArr) {
                MaxArr = Arr;
                Location2=i;
                ;
                }
        }
        
        //用這個算法，通過最后的位置，和最大值來求出起始位置
        for(i=Location2;i>=0;i--)
        {
            if(MaxArr-arr[i]==0)
            {    
                Location1=i;//通過求出來的最大值和最后的那個位置，往前推移，找出起始位置
                break;//跳出循環
            }
            
        }
        /**這種情況的出現當且僅當全部的數字都為負數的時候，
         對所有的數字求一個最大值就是最大子數組**/
        if (MaxArr == 0) {
            for ( i = 0; i < A; i++) {
                if (i == 0) {
                    MaxArr = arr[i];
                }
                if (arr[i] > MaxArr) {
                    MaxArr = arr[i];
                }
            }
        }
        //***************
        System.out.println("子數組的長度為"+(Location2-Location1+1));
        System.out.println("子數組是由第    "+(Location1+1)+"   個數到第    "+(Location2+1)+"  個數組成");
        System.out.println("最大子數組的和是   "+MaxArr);
        
    }
}

驗證截圖