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