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;
}

本栏目推荐文章
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• 类模板实现简单的数组
• IDEA项目名称后面出现中括号，模块Modules的名子和文件夹名称不同，可以右键修改名称也可以在File->Project Structure 修改Modules的Name(快捷键ctrl+Shift+Alt+s)
• 【LeetCode 2701. 连续递增交易】MySQL用户变量编程得到严格递增连续子序列的开始位置，结束位置，长度等统计信息
• python经典有序序列的list列表推导式
• 【Leetcode 2474. 购买量严格增加的客户】MySQL用户变量编程解决严格递增连续子序列问题
• 数组内存图
• 解题报告P2501 [HAOI2006] 数字序列
• 数组
• 小程序开发：笔记详情显示图片以及可以富文本编辑

数组 序列 可以使 长度 个数数组 序列 可以使 长度 数组 长度 位置 序列 变量 长度 树形 数组 函数 可以通过 序列 个数673 字符串 长度 字符 个数 数组 整数 个数nums 数组 矩阵 螺旋 长度 数组 长度leetcode 209 数组 长度209