当前位置 博文首页 > D.monster的博客:2021-03-04 携程实习笔试算法题记录
总共2道算法题120分钟
表达式求值这一类问题一直没有去做,知道要用Stack去做但是不会。。。后续需要加强补。
因为分割的数组是由连续子数组组成,所以可以用dfs来遍历所有情况
private static int res = Integer.MIN_VALUE;
static int maxAmount(int[] packets, int n) {
dfs(packets,n,0,0,Integer.MAX_VALUE);
return res;
}
private static void dfs(int[] packets, int n, int curIndex, int curSum, int curMin){
// 如果不够分则直接返回
if(packets.length-curIndex<n) return;
if(n==0){
for(int i = curIndex ; i < packets.length ; i++) curSum+=packets[i];
curMin = Math.min(curMin,curSum);
res = Math.max(curMin,res);
return;
}
int nextIndex = curIndex+1;
// 把红包纳入前一个红包
int ccurSum = curSum+packets[curIndex];
dfs(packets,n,nextIndex,ccurSum,curMin);
// 开辟新的红包
if(curSum!=0) {
curMin = Math.min(curMin,curSum);
n--;
}
curSum = packets[curIndex];
dfs(packets,n,nextIndex,curSum,curMin);
}
过了两个测试用例
[1,2,3,4,5,6,7,8,9]
5
和
[1,2]
1