一、问题描述

给定一个整数数组 nums，返回最长连续递增序列的长度。

二、方案一：动态规划

1、思路

动态规划的基本思想是，对于数组中的每个元素，如果它大于前一个元素，则更新当前元素的最长连续递增序列长度。

2、代码实现

func findLengthOfLCIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    dp := make([]int, len(nums))
    maxLen := 1
    for i := 0; i < len(nums); i++ {
        dp[i] = 1
        if i > 0 && nums[i] > nums[i-1] {
            dp[i] = dp[i-1] + 1
        }
        maxLen = max(maxLen, dp[i])
    }
    return maxLen
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组。
• 空间复杂度：O(n)，我们需要一个长度为 n 的数组来存储每个元素的最长连续递增序列长度。

三、方案二：贪心算法

1、思路

贪心算法的基本思想是，遍历数组，如果当前元素大于前一个元素，则更新当前的最长连续递增序列长度；否则，重置当前的最长连续递增序列长度。

2、代码实现

func findLengthOfLCIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    maxLen, curLen := 1, 1
    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            curLen++
        } else {
            curLen = 1
        }
        maxLen = max(maxLen, curLen)
    }
    return maxLen
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们只需要遍历一次数组。
• 空间复杂度：O(1)，我们只需要常数级别的额外空间来存储最长连续递增序列长度。

四、总结

方案	时间复杂度	空间复杂度	说明
方案一	O(n)	O(n)	动态规划，易于理解
方案二	O(n)	O(1)	贪心算法，空间复杂度更低
在大多数情况下，方案二的效率更高，因为它不需要额外的空间来存储每个元素的最长连续递增序列长度。