[Java知识库]java实现寻找两个数组的最大子数组

import java.util.Arrays;

public class MaxSubArray {
public static void main(String args[]){
int[] array1 = {1,2,3,5,6};
int[] array2 = {1,2,3,4,5,6};
System.out.println(method2(array1,array2));
}

//滑动窗口
public static int method2(int[] array1,int[] array2){
    //先取出两个数组的长度
    int len1 = array1.length;
    int len2 = array2.length;
    //确定返回值，用于每次循环遍历替换成最大的
    int max = -1;
    int step = 0;
    //选择第一个数组的每一个位置作为初始位置，这是一个数组逐渐减小的过程所以该算法叫做滑动窗口
    //在每一个循环中都需要设计一个另外的函数来对比两个数组中最大相同的为位置
    for(int i = 0;i < len1;i++){
        int min = Math.min(len1 - i,len2);
        step = maxLength(array1,array2,i,0,min);
        if(max < step){
            max = step;
        }
    }
    //需要重新使用第二个数组的每一个位置对准第一个数组
    for(int i = 0;i < len1;i++){
        int min = Math.min(len1,len2 - i);
        step = maxLength(array1,array2,0,i,min);
        if(max < step){
            max = step;
        }
    }

    return max;
}

//返回两个数组中最大连续相同的个数
//这五个参数分别为两个数组，两个数组用于比较的初始位置，其中较小一个数组的长度，我们只需要比较较小数组的次数
public static int maxLength(int[] array1,int[] array2,int index1,int index2,int len){
    int max = -1;
    int length = 0;
    //比较按照顺序比较两个数组的值，如果相同则计数加一，应为是连续相同的个数所以只要有一个不相同就置为0
    for(int i = 0;i < len;i++){
        if(array1[index1 + i] == array2[index2 + i]){
            length++;
        }else{
            length = 0;
        }

        if(max < length){
            max = length;
        }
    }
    return max;
}







//动态规划
public static int[] method1(int array1[],int array2[]){
    //确定动态规划数组的长度,创建动态规划数组
    int length1 = array1.length + 1;
    int length2 = array1.length + 1;
    int dump[][] = new int[length1][length2];

    //用于记录数组中的最大值和最大长度
    int maxLength = -1;
    int index = -1;
    //给动态规划数组赋值，原则为如果两个数相同则为对角线上一个元素的值加1，否则为0
    for(int i = 1;i < length1;i++){
        for(int j = 1;j < length2;j++){
            if(array1[i - 1] == array2[j - 1]){
                dump[i][j] = dump[i - 1][j - 1] + 1;
                //在创建的过程当中记录下来最大子数组的长度和在array1中的最后位置
                if(dump[i][j] > maxLength){
                    maxLength = dump[i][j];
                    index = i - 1;
                }
            }else{
                dump[i][j] = 0;
            }
        }
    }
    //构建返回的数组，如果maxLength始终未改变则说明没有重复部分直接返回null否则按照逆序创建一个数组返回
    if(maxLength == -1){
        return null;
    }else{
        int[] result = new int[maxLength];
        for(int i = 0;i < maxLength;i++){
            result[maxLength - 1 - i] = array1[index - i];
        }
        return result;
    }
}

}