674. Longest Continuous Increasing Subsequence

leetcode easy

#array#csharp#easy#leetcode#math#search#sort

Task

Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.

Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].

Пример:

Input: nums = [1,3,5,4,7]

Output: 3

Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.

Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element

C# solution

matched/original

public class Solution {
    public int FindLengthOfLCIS(int[] nums) {
        int ans = 0, anchor = 0;
        for (int i = 0; i < nums.Length; ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            ans = Math.Max(ans, i - anchor + 1);
        }
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindLengthOfLCIS(vector<int>& nums) {
        int ans = 0, anchor = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            ans = max(ans, i - anchor + 1);
        }
        return ans;
    }
}

Java solution

matched/original

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 0, anchor = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            ans = Math.max(ans, i - anchor + 1);
        }
        return ans;
    }
}

JavaScript solution

matched/original

var findLengthOfLCIS = function(nums) {
    let ans = 0, anchor = 0;
    for (let i = 0; i < nums.length; ++i) {
        if (i > 0 && nums[i - 1] >= nums[i]) {
            anchor = i;
        }
        ans = Math.max(ans, i - anchor + 1);
    }
    return ans;
}

Python solution

matched/original

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        ans = 0
        anchor = 0
        for i in range(len(nums)):
            if i > 0 and nums[i - 1] >= nums[i]:
                anchor = i
            ans = max(ans, i - anchor + 1)
        return ans

Go solution

matched/original

func findLengthOfLCIS(nums []int) int {
    ans, anchor := 0, 0
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i-1] >= nums[i] {
            anchor = i
        }
        if i-anchor+1 > ans {
            ans = i - anchor + 1
        }
    }
    return ans
}

Explanation

Algorithm

Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.

Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.

Возвращаем максимальную длину найденной непрерывной возрастающей подпоследовательности.

😎