LeetCode 解题思路 44（Hot 100）

解题思路：

1. dp 数组的含义： 以 nums[i] 为结尾的最长递增子序列的长度。
2. 递推公式： dp[i] = Math.max(dp[i], dp[j] + 1)。
3. dp 数组初始化： dp[i] = 1。
4. 遍历顺序： 从小到大去遍历，从 i = 1 开始，直到 i = nums.length - 1。
5. 打印 dp 数组

Java代码：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int result = 0;

        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            result = Math.max(result, dp[i]);
        }

        return result;
    }
}

复杂度分析：

• 时间复杂度： O($n^2$)。
• 空间复杂度： O(1)。
  

解题思路：

1. 初始化变量​​：

• maxProduct：记录全局的最大乘积，初始值为数组的第一个元素。
• minProduct：记录当前的最小乘积，初始值为数组的第一个元素。
• result：记录最终的结果，初始值为数组的第一个元素。

2. 遍历数组​​： 对于每个元素 nums[i]，我们需要考虑两种情况：

• 如果 nums[i] 是正数，那么当前的最大乘积可能是 maxProduct $\ast$ nums[i] 或 nums[i] 本身，而最小乘积可能是 minProduct $\ast$ nums[i] 或 nums[i] 本身。
• 如果 nums[i] 是负数，那么当前的最大乘积可能是 minProduct $\ast$ nums[i] 或 nums[i] 本身，而最小乘积可能是 maxProduct $\ast$ nums[i] 或 nums[i] 本身。
• 为了统一处理这两种情况，我们可以先计算 nums[i]、maxProduct $\ast$ nums[i] 和 minProduct $\ast$ nums[i] 的值，然后取其中的最大值和最小值分别作为新的 maxProduct 和 minProduct。

3. 更新结果​​： 在每次迭代中，更新 result 为 maxProduct 和 result 中的较大值。

4. 返回结果​​： 遍历结束后，返回 result。

Java代码：

public class Solution {
    public int maxProduct(int[] nums) {
        int maxProduct = nums[0];
        int minProduct = nums[0];
        int result = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int tempMax = Math.max(nums[i], Math.max(maxProduct * nums[i], minProduct * nums[i]));
            minProduct = Math.min(nums[i], Math.min(maxProduct * nums[i], minProduct * nums[i]));
            maxProduct = tempMax;

            result = Math.max(result, maxProduct);
        }

        return result;
    }
}

复杂度分析：

• 时间复杂度： O(n)。
• 空间复杂度： O(1)。