题目要求求出最多有多少个关卡两个人互相不会嘲笑,也就是当我们求出差分数组(增量)之后,转化为求两个差分数组中相同部分的最长连续子数组。
什么是两个数组相同部分的连续子数组?
假设下标索引i到j是数组a和数组b相同部分的连续子数组,那么对于每一个x(i<=x<=j),ax==bx都是成立的。
例如这两个数组
小红与小堡一块做闯关,每关都会记下各自得分。若甲在本关得分相对前一关上升,乙却相对前一关下降,甲便可讥讽乙。若两人在本关得分都比前一关高,上升幅度更大的那人可讥讽对方;若两人在本关得分都比前一关低,下降幅度更小的那人可讥讽对方。唯有两人上升幅度一样,或下降幅度一样时,才谁也不讥讽谁。
举例来说,设小红首关得分是3,次关得分是9;小堡首关得分是4,次关得分是7,可见小红多出来的分比小堡更多,于是小红能讥讽小堡。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册