j**l
发帖数: 2911 | 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解决。想了半天未果
，请帮忙解答，谢谢。 | m*****g
发帖数: 226 | 2 能不能用首尾两个指针head tail
while(tail != end)
{
tail++;
len++;
sum+=array[tail];
while(sum>Max)
{
sum-=array[head];
len--;
}
if(len>maxLen) maxLen=len;
}
基本思想就是反正要连续的，那就全都走一遍呗 | I*********g
发帖数: 93 | | d****n
发帖数: 233 | 4 1) suppose sum(1->m) >U
2) supoose sum(len-n+1-> len) > U
3) suppose n < m; you can find if there is a shorter path from 1->x and len-
x+1->len with run time O(n) and 1<=x <= n.
【在 j**l 的大作中提到】
: 是Maximum SubArray Sum的变体,这里有几个要求，一个是连续，一个是最长，一个是
: 和小于等于一个定值T
: 假定全部元素的总和是S, 定义U = S - T, 那么试着把这个问题转为等价的补问题: 找
: 首尾两段，长度加起来最短且其和大于等于U，剩下的中间那截自然就是满足题目的最
: 长子数组。
: 有三种情况
: 1) 只有从首开始的一段
: 2) 只有以尾结束的一段
: 3) 首尾两段都有，且不相交
: 对这三种情况取最小就可以解答
| K******g
发帖数: 1870 | 5 没有这么复杂吧？大家看这样做有没有问题？
条件 T={连续和小于或等于S}
假设数组是A，长度为N， L(k)表示从A[k]往前推，符合条件T的子数组的长度， s(k)是子数组的
总和。同时保持一个指针P指向该子数组的起始点。
如果s(k-1)+A[k] > S, 则指针P往前移x步使得s(k-1)+A[k]<=S, L(k) = L(k-1)+1-x.
如果s(k-1)+A[k] <= S, 则L(k) = L(k-1)
最后，遍历L，找出最大的长度。
如果要首尾相接的话，那就不在k=N的时候stop，一直到P越过了a[N-1],然后就stop。
Complexity是O(N)还是O（N^2），有更好的解吗？
【在 j**l 的大作中提到】
: 是Maximum SubArray Sum的变体,这里有几个要求，一个是连续，一个是最长，一个是
: 和小于等于一个定值T
: 假定全部元素的总和是S, 定义U = S - T, 那么试着把这个问题转为等价的补问题: 找
: 首尾两段，长度加起来最短且其和大于等于U，剩下的中间那截自然就是满足题目的最
: 长子数组。
: 有三种情况
: 1) 只有从首开始的一段
: 2) 只有以尾结束的一段
: 3) 首尾两段都有，且不相交
: 对这三种情况取最小就可以解答
| h**k
发帖数: 3368 | 6 你的算法应该是对的，帮你优化以下
两个指针，初始 p_left=0, p_right=0,
if p_right > p_left, sum(p_left,p_right) = sum of A[p_left,...,p_right-1];
if p_right = p_left, sum(p_left,p_right) = 0
step 1:
while ( sum(p_left,p_right) < T || p_right == n )
p_right increase
step 2:
now set A[p_left, p_right-2] is a maximum length set starting from p_left
whose sum <= T; record its length p_right-1-p_left
step 3:
then increase p_left
while( sum(p_left, p_right) > T )
p_left incrase
step 4:
now set A[p_left, p_right-2] i
【在 K******g 的大作中提到】
: 没有这么复杂吧？大家看这样做有没有问题？
: 条件 T={连续和小于或等于S}
: 假设数组是A，长度为N， L(k)表示从A[k]往前推，符合条件T的子数组的长度， s(k)是子数组的
: 总和。同时保持一个指针P指向该子数组的起始点。
: 如果s(k-1)+A[k] > S, 则指针P往前移x步使得s(k-1)+A[k]<=S, L(k) = L(k-1)+1-x.
: 如果s(k-1)+A[k] <= S, 则L(k) = L(k-1)
: 最后，遍历L，找出最大的长度。
: 如果要首尾相接的话，那就不在k=N的时候stop，一直到P越过了a[N-1],然后就stop。
: Complexity是O(N)还是O（N^2），有更好的解吗？
|
|
