算法

动态规划-数组

  1. 两个数组最长公共子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static void main(String[] args) {
        int[] arr1={3,4576,768,3,35,68,7,43};
        int[] arr2={54,67,3,3,768,3,35,564};//768,3,35
        int m=arr1.length;
        int n=arr2.length;
        int[][] dp=new int[m][n];
        int start=0;
        int end=0;
        int maxlen=0;
        for (int i = 1; i <=m ; i++) {
            for (int j = 1; j <=n ; j++) {
                if(arr1[i-1]==arr2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(dp[i][j]>maxlen){
                        maxlen=dp[i][j];
                        start=i-maxlen;
                        end=i;
                    }
                }
            }
        }
        List<Integer> res=new ArrayList<>();
        for(int i=start;i<end;i++){
            res.add(arr1[i]);
        }
        System.out.println(res);
    }
  1. 两个数组最长公共子序列长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void main(String[] args) {
    int[] arr1={1,9999,777777,3,8888888,5,7,9,33333333};
    int[] arr2={12,334,456,87,1,3,5,456,7,9,435,12};
    int m=arr1.length;
    int n=arr2.length;
    int[][] dp=new int[m+1][n+1];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(arr1[i-1]==arr2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    System.out.println(dp[m][n]);
}
  1. 连续子数组之和最大值
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public int maxSubArray(int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int sum=0;
        int res=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            sum=Math.max(sum+nums[i],nums[i]);
            res=Math.max(res,sum);
        }
        return res;
    }
  2. 连续子数组乘积最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    int m=nums.length;
    if(m==0){
        return 0;
    }
    int max=nums[0];
    int min=nums[0];
    int res=nums[0];
    for(int i=1;i<m;i++){
        if(nums[i]<0){
            int tmp=max;
            max=min;
            min=tmp;
        }
        max=Math.max(max*nums[i],nums[i]);
        min=Math.min(min*nums[i],nums[i]);
        res=Math.max(res,max);
    }
    return res;
}
  1. 最长上升子序列
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public int lengthOfLIS(int[] nums) {
        int n=nums.length;
        if(n==0){
            return 0;
        }
        int[] dp=new int[n];
        Arrays.fill(dp,1);
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            res=Math.max(res,dp[i]);
        }
        return res;
    }