2D阵列中的局部最大值可以定义为一个值,使得它的4个邻居都小于或等于它,即,为a[i][j]局部最大值,
a[i+1][j] <= a[i][j]
&& a[i-1][j] <= a[i][j]
&& a[i][j+1] <= a[i][j]
&& a[i+1][j-1] <= a[i][j]
我被要求找到给定2D阵列中的所有局部最大值.
执行此操作的简单方法是遍历所有元素,并检查每个元素是否是局部最大值.这将是O(n ^ 2).虽然我的朋友坚持认为应该存在一个渐近更好的算法,但我觉得你做不到这一点.任何提示？
我正在思考Divide and Conquer的思路,但我觉得如果不经过所有数字就不可能检测出所有的局部最大值,这些数字必然是O(n ^ 2).我是对的还是我错过了什么？
我想解决以下问题:
元素值首先减少然后增加的序列称为V-序列.在有效的V序列中,在递增臂中应该至少有一个元素和至少一个元素.
例如,"5 3 1 9 17 23"是有效的V序列,其在减小臂中具有两个元素,即5和3,并且增加臂中的3个元素即9,17和23.但序列"6 4 2"或"8 10 15"中没有一个是V序列,因为"6 4 2"在增加部分中没有元素,而"8 10 15"在减少部分中没有元素.
通过从序列中删除零个或多个元素来获得序列的子序列.例如,定义"7","2 10","8 2 7 6","8 2 7 10 6"等是"8 2 7 10 6"的有效子序列.
给定N个序列的序列,找到其最长的子序列,即V序列.
我目前有一个O(n ^ 2)解决方案,其中我首先初始化一个数组(m []),使得每个m [i]包含在数组内'i'处开始的最长增长序列.
类似地,我初始化另一个数组(d []),使得每个d [i]包含该点处最长的递减序列ENDING.
这两个操作都需要O(n ^ 2)
我现在浏览这些数组并选择m [i] + d [i] -1的最大值,以满足所需的条件.
我想知道的是 - 是否有O(n lg n)解决方案？因为我的解决方案没有在规定的时间限制内运行.谢谢 :)
代码:
#include<cstdio>
#include<algorithm>
using namespace std;
int m[ 200000 ];
int d[200000 ];
int n;
int arr[200000 ];
void LIS()
{
m[ n-1 ] = 1;
int …这样的陈述是什么意思？
int x = ( { int a; scanf( "%d", &a ); a ; } ) ;
它编译并运行相当于:
int x;
scanf( "%d", &x );
它似乎像某种匿名函数调用或其他东西,但我不确定.我没有遇到像({})以前那样的陈述,我无法在网上找到任何解释.任何帮助将非常感谢,谢谢:)
语境:
这是扩展以下代码中的宏时获得的代码:
#define SI ({int a;scanf("%d",&a);a;});
int x = SI;
这是编程竞赛中某人使用的代码.