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]intvar right [MAXN]intvar ends [MAXN]intvar 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;}
复制代码
评论