java动态规划法求一维数组的和

以下是Java动态规划法求一维数组的和的例子：

public class DynamicProgramming {
    public static void main(String[] args) {
        int[] arr = {1, -2, 3, 10, -4, 7, 2, -5};
        int maxSum = maxSubArray(arr);
        System.out.println("Max sum of subarray: " + maxSum);
    }

    public static int maxSubArray(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        dp[0] = arr[0];
        int maxSum = dp[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}

相关问题

用java动态规划法法解决防卫导弹问题

好的，防卫导弹问题是一个经典的动态规划问题。具体的解决方法如下：

1. 首先，我们定义一个二维数组dp，其中dp[i][j]表示前i个导弹中，最后一枚导弹高度为j时的最大拦截导弹数量。

2. 初始化dp数组，当i=1时，dp[i][j]的值为1，因为只有一枚导弹，所以一定能够拦截。

3. 对于i>1的情况，我们需要找到前i-1枚导弹中高度小于等于j的导弹中，能够拦截的最大数量max。然后，我们可以考虑两种情况：

a) 如果第i枚导弹的高度小于等于j，那么它可以被拦截，此时dp[i][j]的值为max+1。

b) 如果第i枚导弹的高度大于j，那么它不能被拦截，此时dp[i][j]的值为max。

4. 最后，我们需要遍历dp数组，找到最大的dp[i][j]，即为能够拦截的最大导弹数量。

代码如下：

public static int maxIntercept(int[] heights) {
    int n = heights.length;
    int[][] dp = new int[n + 1][heights[n - 1] + 1];
    for(int j = 0; j <= heights[n - 1]; j++) {
        dp[1][j] = 1;
    }
    for(int i = 2; i <= n; i++) {
        int max = 0;
        for(int j = 0; j <= heights[n - i]; j++) {
            if(heights[n - i] <= j) {
                max = Math.max(max, dp[i - 1][j]);
                dp[i][j] = max + 1;
            } else {
                max = Math.max(max, dp[i - 1][j]);
                dp[i][j] = max;
            }
        }
    }
    int res = 0;
    for(int j = 0; j <= heights[n - 1]; j++) {
        res = Math.max(res, dp[n][j]);
    }
    return res;
}

注意，这里假设导弹的高度是递减的，因此需要将数组倒序处理。

用java动态规划法解决防卫导弹问题

好的，防卫导弹问题是一个经典的动态规划问题。具体的解决方法如下：

1. 首先，我们定义一个二维数组dp，其中dp[i][j]表示前i个导弹中，最后一枚导弹高度为j时的最大拦截导弹数量。

2. 初始化dp数组，当i=1时，dp[i][j]的值为1，因为只有一枚导弹，所以一定能够拦截。

3. 对于i>1的情况，我们需要找到前i-1枚导弹中高度小于等于j的导弹中，能够拦截的最大数量max。然后，我们可以考虑两种情况：

a) 如果第i枚导弹的高度小于等于j，那么它可以被拦截，此时dp[i][j]的值为max+1。

b) 如果第i枚导弹的高度大于j，那么它不能被拦截，此时dp[i][j]的值为max。

4. 最后，我们需要遍历dp数组，找到最大的dp[i][j]，即为能够拦截的最大导弹数量。

代码如下：

public static int maxIntercept(int[] heights) {
    int n = heights.length;
    int[][] dp = new int[n + 1][heights[n - 1] + 1];
    for(int j = 0; j <= heights[n - 1]; j++) {
        dp[1][j] = 1;
    }
    for(int i = 2; i <= n; i++) {
        int max = 0;
        for(int j = 0; j <= heights[n - i]; j++) {
            if(heights[n - i] <= j) {
                max = Math.max(max, dp[i - 1][j]);
                dp[i][j] = max + 1;
            } else {
                max = Math.max(max, dp[i - 1][j]);
                dp[i][j] = max;
            }
        }
    }
    int res = 0;
    for(int j = 0; j <= heights[n - 1]; j++) {
        res = Math.max(res, dp[n][j]);
    }
    return res;
}

注意，这里假设导弹的高度是递减的，因此需要将数组倒序处理。