题解 | #连续子数组的最大和(二)#

# 高可读性版本
#
class Solution:

    def LastIdxOfMax(self, lst) -> int:
        max_val: int = max(lst)
        index: int = len(lst) - 1
        while index > 0:
            if lst[index] == max_val:
                break
            index -= 1
        return index

    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        # write code here
        if not array:
            return []

        values = [0 for _ in range(len(array))]
        values[0] = array[0]

        for i in range(1, len(array)):
            curr = values[i - 1] + array[i]
            values[i] = max(curr, array[i])

        end_idx = self.LastIdxOfMax(values)
        bgn_idx = end_idx

        while values[bgn_idx] >= 0 and bgn_idx >= 0:
            bgn_idx -= 1

        return array[bgn_idx + (1 if bgn_idx != end_idx else 0) : (end_idx + 1)]