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)。