Re: 回国2年了,最近被个安全部美女狂追 (转载)# Joke - 肚皮舞运动
j*l
1 楼
是Maximum SubArray Sum的变体,这里有几个要求,一个是连续,一个是最长,一个是
和小于等于一个定值T
假定全部元素的总和是S, 定义U = S - T, 那么试着把这个问题转为等价的补问题: 找
首尾两段,长度加起来最短且其和大于等于U,剩下的中间那截自然就是满足题目的最
长子数组。
有三种情况
1) 只有从首开始的一段
2) 只有以尾结束的一段
3) 首尾两段都有,且不相交
对这三种情况取最小就可以解答
由于首尾两端都是固定的,那么算出那么算出a1...ai的和,以及aj...aN的和,都只要
O(N)时间, 所以1), 2)都是O(N)时间可解的
难办的是3), 据说可以处理一下,用binary search的思想在NlogN解决。想了半天未果
,请帮忙解答,谢谢。
和小于等于一个定值T
假定全部元素的总和是S, 定义U = S - T, 那么试着把这个问题转为等价的补问题: 找
首尾两段,长度加起来最短且其和大于等于U,剩下的中间那截自然就是满足题目的最
长子数组。
有三种情况
1) 只有从首开始的一段
2) 只有以尾结束的一段
3) 首尾两段都有,且不相交
对这三种情况取最小就可以解答
由于首尾两端都是固定的,那么算出那么算出a1...ai的和,以及aj...aN的和,都只要
O(N)时间, 所以1), 2)都是O(N)时间可解的
难办的是3), 据说可以处理一下,用binary search的思想在NlogN解决。想了半天未果
,请帮忙解答,谢谢。