数组算法练习

本文最后更新于：2023年8月2日下午

记录数组刷题方案。

1043. 分隔数组以得到最大和

给你一个整数数组 arr，请你将该数组分隔为长度最多为 k 的一些（连续）子数组。分隔完成后，每个子数组的中的所有值都会变为该子数组中的最大值。

返回将数组分隔变换后能够得到的元素最大和。本题所用到的测试用例会确保答案是一个 32 位整数

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        dp_res = list()
        for index, value in enumerate(arr):
            cur_max = value
            temp_res = value
            for sub_index in range(1, k+1):
                cur_index = index - sub_index
                if cur_index >= 0:
                    cur_max = max(cur_max, arr[cur_index+1])
                    temp_res = max(temp_res, dp_res[cur_index] + cur_max * sub_index)
                else:
                    cur_max = max(cur_max, arr[0])
                    temp_res = max(temp_res, (index + 1) * cur_max)
                    continue
                
            dp_res.append(temp_res)
        return dp_res[-1]