package train
;
import java
.util
.Scanner
;
public class 最大的算式
{
public static void main(String
[] args
){
最大的算式 test
= new 最大的算式
();
Scanner in
= new Scanner(System
.in
);
int n
= in
.nextInt();
int k
= in
.nextInt();
int[] A
= new int[n
];
for(int i
= 0;i
< n
;i
++)
A
[i
] = in
.nextInt();
System
.out
.println(test
.getMax(A
, 0, k
));
}
private long getMax(int [] a
, int i
, int k
) {
if(k
==0) {
return getSum(a
,i
,a
.length
-1);
}
long ans
= 0;
for (int j
= i
; j
< a
.length
; j
++) {
long b
= getSum(a
,i
,j
)*getMax(a
,j
+1,k
-1);
ans
= Math
.max(ans
, b
);
}
return ans
;
}
private long getSum(int [] arr
,int satrt
, int end
) {
long sum
= 0;
for (int j
= satrt
; j
<= end
; j
++) {
sum
+=arr
[j
];
}
return sum
;
}
}
在做的时候能想的出来要分几段，这几段只和再相乘： 比如： 1 2 3 4 5能分成 【1】【23】【45】，也能分成【12】【34】【5】，但是没想出来如何枚举出来每一段， 这个答案巧妙的用递归写了出来，用k来表示还有几段没有乘，在没有的时候直接选择最后剩下的数作为一段。非常精巧。
