gpt4 book ai didi

c - 给定二维矩阵,找到最长的递减数字序列

转载 作者:行者123 更新时间:2023-11-30 21:10:07 25 4
gpt4 key购买 nike

给定一个二维数组,找到最长的递减数字序列。限制条件是:1. 不能对角比较元素。

例如:

56 14 51 58 88
26 94 24 39 41
24 16 8 51 51
76 72 77 43 10
38 50 59 84 81
5 23 37 71 77
96 10 93 53 82
94 15 96 69 9
74 0 62 38 96
37 54 55 82 38

这里的答案是:7

对于下面的矩阵

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

答案是 25,因为我可以时尚地移动 25 -> 24 -> 23 -> 22 -> ....依此类推..直到我达到 1。

有人可以帮我解决这个算法吗?

这是我最初的代码:

int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};

int findSequence(int x, int y)
{
for(int i = 0; i < 4; ++i)
{
int new_x = x + dx[i];
int new_y = y + dy[i];
if(isValid(new_x, new_y) && data[x][y] > data[new_x][new_y])
{
std::cout << "" << data[x][y] << " -> " << data[new_x][new_y] << " ";
int tmp = 1 + findSequence(new_x, new_y, isVisited);
//std::cout << " "<< tmp << " ";
return tmp;
}
}
}

谢谢

最佳答案

您可以使用递归。假设我们想要获得从索引 (i,j) 开始的最大序列。然后,如果 A[i][j] > A[i1][j1](其中 A 是 2D),我们可以向任意第四个方向 (i1,j1) 移动数组。

const int N=50;
int A[N][N];
int res=0; // maximum result

int calc(int i, int j) {
int r=1; // only this element forms a single element sequence
if(A[i][j]>A[i][j+1]) r=max(r, 1+ calc(i, j+1));
if(A[i][j]>A[i][j-1]) r=max(r, 1+ calc(i, j-1));
if(A[i][j]>A[i+1][j]) r=max(r, 1+ calc(i+1, j));
if(A[i][j]>A[i-1][j]) r=max(r, 1+ calc(i-1, j));
res=max(res,r);
return r;
}

复杂度:如果结果存储在二维数组中,其中 m 是行数和 n 列数,则复杂度为 O(mn)。

关于c - 给定二维矩阵,找到最长的递减数字序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31839429/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com