leetcode 1043 Partition Array for Maximum Sum 详解

leetcode 1043 Partition Array for Maximum Sum 详解

这是个典型的DP问题，所以先分拆成小的子问题。
如：arr = [1,15, 7, 9, 2, 5, 10],  k = 3

设 f ( i ) f(i) f(i)存储的是当前数组 a r r [ 0 , . . , i − 1 ] arr[0,..,i-1] arr[0,..,i−1]的解
f ( 0 ) = 0 f(0)=0 f(0)=0                                (1)

i = 0 , a r r [ 0 ] = 1 , 则 f ( 1 ) = 1 i = 0, arr[0]=1, 则f(1)=1 i=0,arr[0]=1,则f(1)=1                      (2)

i = 1 , a r r [ 1 ] = 15 , f ( 2 ) = m a x ( f ( 0 ) + 2 ∗ m a x ( a r r [ 0 , . , 1 ] ) , f ( 1 ) + 1 ∗ a r r [ 1 ] ) = 30 i=1, arr[1]=15, f(2) = max(f(0)+2*max(arr[0,.,1]), f(1)+1*arr[1])=30 i=1,arr[1]=15,f(2)=max(f(0)+2∗max(arr[0,.,1]),f(1)+1∗arr[1])=30                          (3)


i = 2 , a r r [ 2 ] = 7 , 则 f ( 3 ) = m a x ( f ( 0 ) + 3 ∗ m a x ( a r r [ 0 , . , 2 ] ) , f ( 1 ) + 2 ∗ m a x ( a r r [ 1 , . , 2 ] ) , f ( 2 ) + a r r [ 2 ] ) = 40 i=2, arr[2]=7, 则f(3)=max(f(0)+3*max(arr[0,.,2]), f(1)+2*max(arr[1,.,2]), f(2)+arr[2])=40 i=2,arr[2]=7,则f(3)=max(f(0)+3∗max(arr[0,.,2]),f(1)+2∗max(arr[1,.,2]),f(2)+arr[2])=40              (4)


i = 3 , a r r [ 3 ] = 9 , 则 f ( 4 ) = m a x ( f ( 1 ) + 3 ∗ m a x ( a r r [ 1 , . , 3 ] ) , f ( 2 ) + 2 ∗ m a x ( a r r [ 2 , . , 3 ] ) , f ( 3 ) + a r r [ 3 ] ) = 54 i=3, arr[3] = 9, 则f(4) = max(f(1)+3*max(arr[1,.,3]), f(2)+2*max(arr[2,.,3]),f(3)+arr[3]) = 54 i=3,arr[3]=9,则f(4)=max(f(1)+3∗max(arr[1,.,3]),f(2)+2∗max(arr[2,.,3]),f(3)+arr[3])=54             (5)
. . .
. . .

从上述例子中可以得出一个方程式：

f ( i ) = m a x ( f ( i − j ) + j ∗ c u r _ m a x ) f(i) = max(f(i-j) + j * cur\_max) f(i)=max(f(i−j)+j∗cur_max) j ∈ [ 1 , m i n ( i , k ) ] j \in [1, min(i,k)] j∈[1,min(i,k)]

最后代码如下：