2023-08-24：请用go语言编写。给定一个长度为n的数组arr，

现在你有一次机会, 将其中连续的K个数全修改成任意一个值，

请你计算如何修改可以使修改后的数 列的最长不下降子序列最长。

请输出这个最长的长度。

最长不下降子序列:子序列中的每个数不小于在它之前的数。

1 <= k, n <= 10^5，

1 <= arr[i] <= 10^6。

来自左程云。

答案2023-08-24：

以下是大致的步骤描述：

1.定义常量MAXN为100001，声明全局数组和变量：arr、right、ends、n和k。这些数组和变量将用于存储计算过程中的中间结果和输入数据。

2.在main函数中设置给定的输入数据：n表示数组的长度为5，k表示连续的k个数需要修改，arr存储具体的数组元素。

3.判断如果k大于等于n，则无需做修改，直接输出n作为最长不下降子序列的长度。

4.否则，调用rightFn函数计算修改后的数组中以每个元素为结尾的最长不下降子序列的长度，并将结果存储在数组right和ends中。

5.调用getAns函数计算修改后的数组的最长不下降子序列的长度，并输出结果。

rightFn函数的步骤描述：

1.初始化right数组的最后一个元素right[n]为1，表示以最后一个元素为结尾的最长不下降子序列的长度为1。

2.初始化ends数组的第一个元素ends[1]为arr[n]，表示以最后一个元素为结尾的最长不下降子序列的最后一个元素为arr[n]。

3.初始化len为1，表示当前得到的最长不下降子序列的长度为1。

4.从倒数第二个元素开始，循环遍历数组arr，通过二分查找的方式找到以arr[i]为结尾的最长不下降子序列的长度。

5.使用二分查找的辅助数组ends，找到大于arr[i]的第一个元素位置find。

6.将arr[i]赋值给ends[find]，更新当前的最长不下降子序列的长度为max(len, find)，并将结果存储在right[i]中。

7.循环结束后，right数组存储了以每个元素为结尾的最长不下降子序列的长度。

getAns函数的步骤描述：

1.初始化ans为0，表示当前的最长不下降子序列的长度为0。

2.初始化len为0，表示当前最长不下降子序列的长度为0。

3.从第k+1个元素开始，循环遍历数组arr，计算修改后的数组的最长不下降子序列的长度。

4.使用二分查找的方式找到arr[i]在ends数组中的位置find。

5.更新ans为max(ans, find+right[i]-1+k)。其中，find表示以arr[i]为结尾的最长不下降子序列的长度，right[i]表示以arr[i]为起点的最长不下降子序列的长度，k表示连续的k个数被修改。

6.使用二分查找的辅助数组ends，找到大于arr[j]的第一个元素位置find（这里j为i-k）。

7.将arr[j]赋值给ends[find]，更新当前的最长不下降子序列的长度为max(len, find)。

8.循环结束后，ans存储了修改后的数组的最长不下降子序列的长度。

9.返回ans作为结果。

总的时间复杂度为O(n log n)，其中n为数组的长度，主要是由二分查找的过程引起的。

总的额外空间复杂度为O(n)，主要是由数组的存储引起的。

go完整代码如下：

package main

import (
    "fmt"
)

const MAXN = 100001

var arr [MAXN]int
var right [MAXN]int
var ends [MAXN]int
var n, k int

func main() {

    n = 5
    k = 1
    arr[1] = 1
    arr[2] = 4
    arr[3] = 2
    arr[4] = 8
    arr[5] = 5

    if k >= n {
        fmt.Println(n)
    } else {
        rightFn()
        fmt.Println(getAns())
    }
}

func rightFn() {
    right[n] = 1
    ends[1] = arr[n]
    len := 1

    for i := n - 1; i > 0; i-- {
        l := 1
        r := len
        find := len + 1

        for l <= r {
            m := (l + r) / 2
            if ends[m] < arr[i] {
                find = m
                r = m - 1
            } else {
                l = m + 1
            }
        }

        ends[find] = arr[i]
        len = max(len, find)
        right[i] = find
    }
}

func getAns() int {
    ans := 0
    len := 0

    for i, j := k+1, 1; i <= n; i, j = i+1, j+1 {
        l := 1
        r := len
        find := len + 1

        for l <= r {
            m := (l + r) / 2
            if ends[m] > arr[i] {
                find = m
                r = m - 1
            } else {
                l = m + 1
            }
        }

        ans = max(ans, find+right[i]-1+k)

        l = 1
        r = len
        find = len + 1

        for l <= r {
            m := (l + r) / 2
            if ends[m] > arr[j] {
                find = m
                r = m - 1
            } else {
                l = m + 1
            }
        }

        len = max(len, find)
        ends[find] = arr[j]
    }

    ans = max(ans, len+k)
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

rust完整代码如下：

const MAXN: i32 = 100001;

static mut ARR: [i32; MAXN as usize] = [0; MAXN as usize];
static mut RIGHT: [i32; MAXN as usize] = [0; MAXN as usize];
static mut ENDS: [i32; MAXN as usize] = [0; MAXN as usize];
static mut N: i32 = 0;
static mut K: i32 = 0;

fn main() {
    unsafe {
        N = 5;
        K = 1;
        ARR[1] = 1;
        ARR[2] = 4;
        ARR[3] = 2;
        ARR[4] = 8;
        ARR[5] = 5;

        if K >= N {
            println!("{}", N);
        } else {
            right_fn();
            println!("{}", get_ans());
        }
    }
}

fn right_fn() {
    unsafe {
        RIGHT[N as usize] = 1;
        ENDS[1] = ARR[N as usize];
        let mut len: i32 = 1;

        let mut i = N - 1;
        while i >= 0 {
            let mut l = 1;
            let mut r = len;
            let mut find = len + 1;

            while l <= r {
                let m = (l + r) / 2;
                if ENDS[m as usize] < ARR[i as usize] {
                    find = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }

            ENDS[find as usize] = ARR[i as usize];
            len = max(len, find);
            RIGHT[i as usize] = find;
            i -= 1;
        }
    }
}

fn get_ans() -> i32 {
    let mut ans = 0;
    let mut len = 0;

    unsafe {
        let mut i = K + 1;
        let mut j: i32 = 1;
        while i <= N {
            let mut l: i32 = 1;
            let mut r = len;
            let mut find = len + 1;

            while l <= r {
                let m = (l + r) / 2;
                if ENDS[m as usize] > ARR[i as usize] {
                    find = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }

            ans = max(ans, find + RIGHT[i as usize] - 1 + K);

            l = 1;
            r = len;
            find = len + 1;

            while l <= r {
                let m = (l + r) / 2;
                if ENDS[m as usize] > ARR[j as usize] {
                    find = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }

            len = max(len, find);
            ENDS[find as usize] = ARR[j as usize];
            i += 1;
            j += 1;
        }

        ans = max(ans, len + K);
    }

    ans
}

fn max(a: i32, b: i32) -> i32 {
    if a > b {
        a
    } else {
        b
    }
}

c++完整代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 100001;

int arr[MAXN] = { 0 };
int right0[MAXN] = { 0 };
int ends0[MAXN] = { 0 };
int n, k;

int max(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}

void rightFn() {
    right0[n] = 1;
    ends0[1] = arr[n];
    int len = 1;

    for (int i = n - 1; i > 0; i--) {
        int l = 1;
        int r = len;
        int find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends0[m] < arr[i]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        ends0[find] = arr[i];
        len = max(len, find);
        right0[i] = find;
    }
}

int getAns() {
    int ans = 0;
    int len = 0;

    for (int i = k + 1, j = 1; i <= n; i++, j++) {
        int l = 1;
        int r = len;
        int find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends0[m] > arr[i]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        ans = max(ans, find + right0[i] - 1 + k);

        l = 1;
        r = len;
        find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends0[m] > arr[j]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        len = max(len, find);
        ends0[find] = arr[j];
    }

    ans = max(ans, len + k);
    return ans;
}

int main() {
    n = 5;
    k = 1;
    arr[1] = 1;
    arr[2] = 4;
    arr[3] = 2;
    arr[4] = 8;
    arr[5] = 5;

    if (k >= n) {
        cout << n << endl;
    }
    else {
        rightFn();
        cout << getAns() << endl;
    }

    return 0;
}

c完整代码如下：

#include <stdio.h>

#define MAXN 100001

int arr[MAXN];
int right[MAXN];
int ends[MAXN];
int n, k;

int max(int a, int b) {
    return (a > b) ? a : b;
}

void rightFn() {
    right[n] = 1;
    ends[1] = arr[n];
    int len = 1;

    for (int i = n - 1; i > 0; i--) {
        int l = 1;
        int r = len;
        int find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends[m] < arr[i]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        ends[find] = arr[i];
        len = max(len, find);
        right[i] = find;
    }
}

int getAns() {
    int ans = 0;
    int len = 0;

    for (int i = k + 1, j = 1; i <= n; i++, j++) {
        int l = 1;
        int r = len;
        int find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends[m] > arr[i]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        ans = max(ans, find + right[i] - 1 + k);

        l = 1;
        r = len;
        find = len + 1;

        while (l <= r) {
            int m = (l + r) / 2;
            if (ends[m] > arr[j]) {
                find = m;
                r = m - 1;
            }
            else {
                l = m + 1;
            }
        }

        len = max(len, find);
        ends[find] = arr[j];
    }

    ans = max(ans, len + k);
    return ans;
}

int main() {
    n = 5;
    k = 1;
    arr[0] = 0;
    arr[1] = 1;
    arr[2] = 4;
    arr[3] = 2;
    arr[4] = 8;
    arr[5] = 5;

    if (k >= n) {
        printf("%d\n", n);
    }
    else {
        rightFn();
        printf("%d\n", getAns());
    }
    return 0;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接