Javaは最大連続サブ配列と


1問題は、正、負、ゼロの配列を持つ整数配列を記述します.配列内の連続する1つ以上の整数は、1つのサブ配列を構成し、各サブ配列には1つの和があります.すべてのサブ配列の和の最大値を求めます.例えば、入力された配列が{1,−2,3,10,−4,7,2,−5}であり、最大のサブ配列が{3,10,−4,7,2}である場合、出力はそのサブ配列の和18となる.
2ソリューション2.1蛮力列挙法
package com.liuzhen.array_2;

public class MaxSubArray {
    
    public int bruteMethod(int[] A){
        int maxResult = A[0];        
        int maxTemp = 0;;
        for(int i = 0;i < A.length;i++){
            for(int j = i;j < A.length;j++){
                for(int k = i;k <= j;k++){
                    maxTemp += A[k];
                }
                if(maxTemp > maxResult)
                    maxResult = maxTemp;
                maxTemp = 0;             //          ,     0
            }
        }
        return maxResult;
    }
    
    public static void main(String[] args){
        MaxSubArray test = new MaxSubArray();
        int[] A = {1,-2,3,10,-4,7,2,10,-5,4};
        System.out.println("         A          :"+test.bruteMethod(A));
    }
}


2.2動的計画法
package com.liuzhen.array_2;

public class MaxSubArray {
    
    public int dynaticMethod(int[] A){
        int maxResult = A[0];   
        int maxTemp = 0;
        for(int i = 0;i < A.length;i++){
            if(maxTemp >= 0)
                maxTemp += A[i];
            else
                maxTemp = A[i];
            if(maxTemp > maxResult)
                maxResult = maxTemp;
        }
        return maxResult;
    }
    
    public static void main(String[] args){
        MaxSubArray test = new MaxSubArray();
        int[] A = {1,-2,3,10,-4,7,2,10,-5,4};
        System.out.println("           A          :"+test.dynaticMethod(A));
    }
}