区间最小数乘区间和的最大值

# -*- coding: utf-8 -*-


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param a int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/f31ec24143c549fcbbfafad1d480c393?tpId=196&tqId=40511&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：woshifeiwu
    算法：
        本题要求计算：区间和 * 区间最小数，针对这两点，我们分别处理。
        1. 对于区间和，我们构造前缀和列表dp。设dp[i]表示以a[i]结尾的前缀和
            初始化：
                dp[0] = a[0]
            状态转移方程：
                dp[i] = dp[i - 1] + a[i]
            有了前缀和区间之后，对于任意闭区间[i, j]，区间和为dp[j] - dp[i]
        2. 对于区间最小数，我们维护一个单调递增的栈stack，栈内存储的是元素下标
            遍历列表a：
                如果当前元素小于栈顶元素，入栈；
                否则，出栈，计算当前 区间和 * 区间最小数，更新res
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n)
    """

    def mintimessum(self, a):
        # write code here
        n = len(a)

        dp = [0] * n
        dp[0] = a[0]
        for i in range(1, n): # 建立列表a的前缀和
            dp[i] = dp[i - 1] + a[i]

        stack, res = [], 0
        for i in range(n):
            while stack and a[i] < a[stack[-1]]:
                idx = stack.pop()
                winSum = dp[stack[-1]] if stack else 0
                res = max(res, a[idx] * (dp[i - 1] - winSum)) # 当前区间为[idx, right], right = i - 1，区间和为：dp[right] - dp[stack[-1]]，这里需要注意当stack为空
            stack.append(i)

        while stack:
            idx = stack.pop()
            winSum = dp[stack[-1]] if stack else 0
            res = max(res, a[idx] * (dp[n - 1] - winSum))

        return res


if __name__ == "__main__":
    sol = Solution()

    # a = [1, 2, 3, 4, 5]

    a = [1, 1, 1, 1, 1]

    res = sol.mintimessum(a)

    print res