如何求数对之差的最大值？

数据结构与算法

题目描述，数组中的一个数字减去右边子数组中的一个数字可以得到一个差值，所所得可能差值中的最大值

1.首发----我的dp

保留前面子数组中的最大值就可以了

public class Solution {
    public int getMax(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = 0;
        int temp;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i]);
            if (dp[i] != nums[i]) {
                temp = dp[i] - nums[i];
                if (temp > max) {
                    max = temp;
                }
            }
        }
        System.out.println("result :" + max);
        return max;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 10, 4, 100, 5, 6, 6};
        solution.getMax(nums);
    }
}

2.空间优化的动态规划

dp[i]和dp[i-1]是两个不同的状态，可以不保留，用同一变量的不同位置来表示不同的状态

public class Solution {
    public int getMax(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int dp = nums[0];
        int max = 0;
        int temp;
        for (int i = 1; i < nums.length; i++) {
            dp = Math.max(dp, nums[i]);
            if (dp != nums[i]) {
                temp = dp - nums[i];
                if (temp > max) {
                    max = temp;
                }
            }
        }
        System.out.println("result :" + max);
        return max;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 2, 10, 4, 100, 5, 6, 6};
        solution.getMax(nums);
    }
}