要能够组成三角形,需要满足任意两边之和大于第三边的条件。而如果一个连续子序列中任意三个数都满足这个条件,则需要该区间中最小的两个值的和大于最大值。该需求可以考虑使用双指针进行求解。
从1到i枚举右指针,并维护左指针。左指针的变化要求指针间所有数中,最小的两个值的和要大于指针间所有数中最大的值,因此在将第i个数加入时,动态移动左指针以满足要求。
给定一个长度为 n 的正整数序列 a1,a2,…,an。
定义一段连续子区间 [l,r] 是“和谐的”,当且仅当从该区间中任选三个不同位置的元素,将它们按升序排列为 x≤y≤z 后,都满足严格不等式 x+y>z。
请你找出最长的和谐区间,并输出其左右端点。如果有多个最长的和谐区间,请输出左端点最小的那一个。
保证输入数据合法且答案存在。
约束:
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.