分割数组以得最大和的题解
分隔数组以得到最大和
d p [ i ] dp[i] dp[i]表示前i个数字的最大和，k种转移。
d p [ i ] = m a x { d p [ i − 1 ] + 1 ∗ m a x { a r r [ i ] } d p [ i − 2 ] + 2 ∗ m a x { a r r [ i ] , a r r [ i − 1 ] } . . . k ∗ d p [ i − k ] + m a x { a r r [ i ] , a r r [ i − 1 ] , . . . a r r [ i − k + 1 ] } } \\begin{equation} \\begin{aligned} dp[i] = max\\{ \\\\ & dp[i - 1] + 1 * max \\{ arr[i]\\}\\\\ &dp[i - 2] + 2 * max \\{arr[i], arr[i - 1]\\} \\\\& ... \\\\ &k * dp[i - k] + max \\{arr[i], arr[i - 1], ... arr[i - k + 1] \\} \\\\ \\} \\end{aligned} \\end{equation} dp[i]=max{}dp[i−1]+1∗max{arr[i]}dp[i−2]+2∗max{arr[i],arr[i−1]}...k∗dp[i−k]+max{arr[i],arr[i−1],...arr[i−k+1]}
d p [ i ] = m a x ( d p [ i − j ] + j ∗ m a x ( a r r [ i ] . . . a r r [ i − j + 1 ] ) ) = m a x { d p [ i − j ] + j ∗ m a x { a r r [ t ] } } j ∈ [ 1 , m i n ( k , i ) ] , t ∈ [ i − j + 1 , i ] \\begin{equation} \\begin{aligned} dp[i] &= max(dp[i - j] + j * max(arr[i]... arr[i - j + 1])) \\\\ & =max\\{dp[i - j] + j * max\\{arr[t]\\}\\} \\\\ & j \\in[1, min(k, i)],t\\in[i-j + 1, i] \\end{aligned} \\end{equation} dp[i]=max(dp[i−j]+j∗max(arr[i]...arr[i−j+1]))=max{dp[i−j]+j∗max{arr[t]}}j∈[1,min(k,i)],t∈[i−j+1,i]