Daily 20/01/2024: [907. Sum of Subarray Minimums](https://leetcode.com/problems/k-inverse-pairs-array/)

# 1. Tóm tắt đề bài
Cho một mảng các số nguyên ```arr```, hãy tìm tổng của ```min(b)```, trong đó b là các mảng con (liên tiếp) của ```arr```.
Trả về kết quả theo modulo $10^9 + 7$.

#### Giới hạn
- $1 \le$ ```arr.length``` $\le 3 \cdot 10^4$
- $1 \le$ ```arr[i]``` $\le 3 \cdot 10^4$

# 2. Tóm tắt lời giải

#### Phân tích
- Trước hết nếu mà chúng ta làm theo phương pháp chạy trâu, độ phức tạp có thể lên tới $O(n^3)$ hoặc cải tiến hơn bằng các cấu trúc dữ liệu khác như Segment Tree hay RMQ thì cũng sẽ không cải thiện lắm.
- Vì vậy cần nghĩ ra hướng giải khác, nhận xét rằng 1 vị trí ở mảng có thể làm min của rất nhiều mảng con, vì vậy chúng ta cần khai thác ở điểm này. Nó sẽ hướng chúng ta đến một bài toán quy hoạch động cơ bản. Lưu ý là các mảng con là các dãy liên tiếp.
- Thật vậy nếu ta xét ```dp[i]``` là tổng của tất cả các mảng con liên tiếp có chứa ```arr[i]```. Sẽ có 2 trường hợp xảy ra:
- ```arr[i]``` nhỏ nhất trong ```arr[0...i]``` khi đó ```dp[i]``` đơn giản là ```(i + 1) * arr[i]``` vì có ```i + 1``` mảng con chứa ```i```.
- Tồn tại ```k``` mà ```arr[i]``` nhỏ nhất trong ```arr[k..i]``` như vậy với các mảng con từ ```arr[0..i]``` cho tới ```arr[k..i]``` thì sẽ có tổng các min là bài toán con ```dp[k]``` và từ ```arr[k + 1: ...i]``` tới ```arr[i..i]``` có tổng các min là ```arr[i] * (i - k)``` vì ```arr[i]``` nhỏ nhất khi xét các mảng con đấy.

- Kết quả của bài toán sẽ tổng của tất cả các ```dp[i]```.
# 3. Lời giải chi tiết
- Xây dựng 1 stack để tìm được phần tử k mà ```arr[i]``` nhỏ nhất trong ```arr[k..i]```

#### Code

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        stack = []
        result = 0
        mod = 10 ** 9 + 7
        dp = [0] * len(arr)


        for i in range(len(arr)):
            while stack and arr[i] <= arr[stack[-1]]:
                stack.pop()
            
            if stack:
                j = stack[-1]
                dp[i] = dp[j] + arr[i] * (i - j)
            else:
                dp[i] =  arr[i] * (i + 1)

            result += dp[i]
            result %= mod
            stack.append(i)
        
        return result

#### Độ phức tạp
$O(n)$
# 4. Kết luận & gợi ý mở rộng
- Bài này khá hay về tính vận dụng
> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Hash Map</span>