---
# System prepended metadata

title: 1793. Maximum Score of a Good Subarray
tags: [Leetcode, Two Pointers, Hard, Greedy]

---

# 1793. Maximum Score of a Good Subarray
###### tags: `Leetcode` `Hard` `Two Pointers` `Greedy`
Link: https://leetcode.com/problems/maximum-score-of-a-good-subarray/
## 思路
思路不难 但是有很多edge case需要考虑
感觉参考了[0084. Largest Rectangle in Histogram](https://hackmd.io/dE8-j_vvRq-zByLqRb7z7g)的思路
首先找到中心点，然后将左右两个指针出现的数字进行比较
哪边大就先往哪边走 然后更新答案

由于两边如果只有一边停了也可以接着跑
所以edge case比较多
分四种情况考虑:
1. 两边都不能动 直接break
2. left能动 right不行 一定是动left
3. right能动 left不行 动right
4. 两边都能动 比较两边的大小

但基本上这种情况 判断往哪边走都需要放在更新结果前面 所以为了让更新结果的时候不要有溢出的情况最外层while回圈的条件是l>0而不是l=0，r同理
## Code
java
```java=
class Solution {
    public int maximumScore(int[] nums, int k) {
        int score=nums[k];
        int l=k, r=k, min=nums[k];
        while(l>0 || r<nums.length-1){
            if(l==0){
                ++r;
            }
            else if(r==nums.length-1){
                --l;
            }
            else if(nums[l-1]>nums[r+1]){
                --l;
            }
            else{
                ++r;
            }
            min = Math.min(min, Math.min(nums[l], nums[r]));
            score = Math.max(score, min*(r-l+1));
        }
        return score;
    }
}
```
c++
```cpp=
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int l = k, r = k;
        int n = nums.size();
        int ans = nums[k];
        int minNum = nums[k];
        while(l>0 || r<n-1){
            if(l>0 && r<n-1){
                if(nums[l-1]>nums[r+1]) l--;
                else r++;
            }
            else if(l>0) l--;
            else r++;
            minNum = min(minNum, min(nums[l], nums[r]));
            ans = max(ans, (r-l+1)*minNum);
        }
        return ans;
    }
};
```
python
```python=
class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        score = nums[k]
        l = r = k
        minVal = nums[k]
        while l>0 or r<len(nums)-1:
            if l==0:
                r += 1
            elif r == len(nums)-1:
                l -= 1
            elif nums[l-1]<nums[r+1]:
                r += 1
            else:
                l -= 1
            minVal = min(minVal, nums[l], nums[r])
            score = max(score, minVal*(r-l+1))
        return score
```