09-动态规划算法

实现一个动态规划算法，并分析其时间复杂度和空间复杂度。

public class DynamicProgrammingExample {
    public static int maxSubArray(int[] nums) {
        int n = nums.length;
        // 定义dp数组，其中dp[i]表示以第i个元素结尾的最大子序和
        int[] dp = new int[n];
        // 初始化dp数组
        dp[0] = nums[0];
        // 定义最大值变量max，初始化为dp[0]
        int max = dp[0];

        for (int i = 1; i < n; i++) {
            // 动态转移方程
            // 如果dp[i-1]<0，则从当前位置i重新开始计算子数组，因为加上之前的负数反而会让和更小
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
            max = Math.max(max, dp[i]);
        }

        return max;
    }
}

代码中实现了一个求解最大子序和的动态规划算法。算法的思想是先定义一个状态数组dp，然后通过遍历原始数组来不断更新状态数组，最终得到最优解。

时间复杂度分析：

对于这个算法，我们需要遍历一遍整个原始数组，所以时间复杂度为O(n)，其中n是数组的长度。

空间复杂度分析：

算法的空间复杂度主要来自于状态数组dp，它需要存储原始数组中每个位置的最大子序和。所以空间复杂度为O(n)，其中n是数组的长度。

验证：

public static void main(String[] args) {
    int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int result = maxSubArray(nums);
    System.out.println(result);
}