Skip to content

Latest commit

 

History

History

1793.Maximum-Score-of-a-Good-Subarray

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

1793.Maximum-Score-of-a-Good-Subarray

注意到这个区间内的所有元素都是正数,那么在固定了minVal的情况下,自然是希望区间越大越好。既然这个区间必须包括k,那么我们首先考虑k为minVal的最大区间范围,往左右分别推至[l,r],得到一个初始答案nums[k]*(r-l+1).

此时区间如果还想外扩,那么minVal必然会进一步降低。此时有两个选择,分别是nums[l]和nums[r]:此时我们应该选较大的那一个,目的是保证能够遍历到minVal每一个可能的取值。类似地,我们每个回合都取下一个次小的minVal,然后将区间往两边扩大一点,计算和更新objective。直至两边的指针都越界为止。