LitCode--最大サブアレイIII
LitCode--maximm-subarray-iii(最大サブアレイIII)
ソースリンク:http://www.lintcode.com/zh-cn/problem/maximum-subarray-iii/
一つの整数配列と一つの整数kを与えて、それらの最大および最大を可能にするk個の重複しないサブアレイを探し出す.
各サブ配列の数字は、配列内の位置に連続しているはずである.
最大の和を返します.
実際の面接でこの問題にあったことがありますか?
はい
サンプル
配列[-1,4,-2,3,-2,3]とk=2を与え、8を返します.
注意
サブアレイは少なくとも一つの数を含んでいます.
挑戦する
要求時間の複雑さはO(n)である.
分析:
O時間しかできません.
musstThe Last[i][j]は、前のi個の数の中でj個のサブアレイの最大のサブアレイと、第i番目の数はj番目のサブアレイの要素である.
notThe Last[i][j]は、前のi個の数の中でj個のサブアレイの最大のサブアレイとを表し、i番目の数は必ずしもj番目のサブアレイの要素ではない.
***時間複雑度O(nk)、 空間複雑度O(nk)****
コード(Python):
ソースリンク:http://www.lintcode.com/zh-cn/problem/maximum-subarray-iii/
一つの整数配列と一つの整数kを与えて、それらの最大および最大を可能にするk個の重複しないサブアレイを探し出す.
各サブ配列の数字は、配列内の位置に連続しているはずである.
最大の和を返します.
実際の面接でこの問題にあったことがありますか?
はい
サンプル
配列[-1,4,-2,3,-2,3]とk=2を与え、8を返します.
注意
サブアレイは少なくとも一つの数を含んでいます.
挑戦する
要求時間の複雑さはO(n)である.
分析:
O時間しかできません.
musstThe Last[i][j]は、前のi個の数の中でj個のサブアレイの最大のサブアレイと、第i番目の数はj番目のサブアレイの要素である.
notThe Last[i][j]は、前のi個の数の中でj個のサブアレイの最大のサブアレイとを表し、i番目の数は必ずしもj番目のサブアレイの要素ではない.
***時間複雑度O(nk)、 空間複雑度O(nk)****
コード(Python):
class Solution:
"""
@param nums: A list of integers
@param k: An integer denote to find k non-overlapping subarrays
@return: An integer denote the sum of max k non-overlapping subarrays
"""
def maxSubArray(self, nums, k):
# write your code here
#mustTheLast[i][j] repesent the number i of nums must be the last number in the j-th subarrays.
#notTheLast[i][j] repesent the number i of nums can be the last number in the j-th subarrays or not.
n = len(nums)
mustTheLast = [[-1e9 for i in range(k+1)] for j in range(n+1)]
notTheLast = [[-1e9 for i in range(k+1)] for j in range(n+1)]
mustTheLast[0][0] = 0
notTheLast[0][0] = 0
for i in range(1, n+1):
mustTheLast[i][0] = 0
notTheLast[i][0] = 0
for j in range(1, k+1):
mustTheLast[i][j] = max(notTheLast[i-1][j-1] + nums[i-1], mustTheLast[i-1][j] + nums[i-1])
notTheLast[i][j] = max(mustTheLast[i][j], notTheLast[i-1][j])
return notTheLast[n][k]