|
H*M
发帖数: 1268 | 2 原楼主的方法好像是对的
现算一个maxconsum,再算minconsum（对非circular）,再用sum-minconsum,比谁大
没想到有什么不妥的地方。 好像也能用同样的方法算minconsum.. |
|
w********p
发帖数: 948 | 3 俺嘬觉得O(1)space 还是可以的
1。 先说说普通non-circle array. 可以用非dynamic programing O(n)runing time,
O(1) space 。 关键是sum<0时，就drop, goto next
2. circle array, 向楼上说的在负数那段开，记住当前maxSum开始的 index,
计算到end of array 时继续，一直到one element before 当前maxSum开始的 index
ex1: -3, 5, 2, 1, 4, => 一只计算到5, 2, 1, 4, -3 got solution 5, 2, 1 , 4
ex2: −2, 1, −3, 4, −1, 2, 1, −2, 4 => 当前maxSum开始
4, −1, 2, 1, −2, 4, -2, 1, -3 got solution 4, -1, 2, 1, -2, 4 |
|
H*M
发帖数: 1268 | 4 我觉得楼主本来的idea就很好
至少我还没看出破绽
,
4 |
|
|
|
k***e
发帖数: 556 | 7 晕 我贴了很长时间没人理
有mm（或貌似mm id）的回帖就立马一堆人回
看来弄个马甲很有必要
ps，我以为人人都知道给定 one dim array，找连续的sub array使得和最大
：）因为在programming pearl和许多算法课的作业里出现过
结果。。。
再次推荐没有读过 变成珍珠 读下这本书 |
|
s*x
发帖数: 3328 | 8 no, it is f(i) = max(a_i, f(i-1)+a_i, f(i-1))
and sure it is linear time algorithm no matter whether the array is circular
or not. the circular case can be treated as array. not so precisely
speaking:
a b c d - circular case is ALMOST equivalent to solve a b c d a b c d - non-
circular, since any factor of the circular word is a factor of that normal
word.
space |
|
l***i
发帖数: 632 | 9
Obviously you shouldn't do that...
You may connect disconnected pieces by adding f(i-1) there...
It's true that you need an O(n) scan to return max f(i) as the final answer.
.. |
|
l***i
发帖数: 632 | 10 enn... minsum(a1,...,an) = -maxsum(-a1,...,-an)...
This is just theoretical analysis (re-using an existing argument always
keeps proofs simple) -- One needn't implement it in this way though... |
|
g*******y
发帖数: 1930 | 11 我觉得那个suggest solution有问题
我觉得这个题目是一个另外一个经典题目的隐藏变形版，什么题目呢，就是前阵子在版
上讨论过的，一个循环数组，求子数组max sum
考虑逆时针和顺时针，应该有两个循环数组
一个循环数组的元素是x[i] = p_i - d_i
另外一个循环数组的元素是x[i]' = p_i - d_(i-1)
这个题目可以等效为，在上面的循环数组中找一个起点x[k]，使得
x[k]>=0,
x[k]+x[k+1]>=0
x[k]+x[k+1]+x[k+2]>=0
...
x[k]+...x[n]+x[1]+...x[k-2]>=0
起点x[k]选在能给出Max sum的subarray的起点，是一个贪心解。 |
|
g*******y
发帖数: 1930 | 12 找出所有根，分段积分，然后得到一个正负数相间的数组，找最大subarray sum嘛
不过这题有些无聊，找所有的根就不是个容易的事情了，然后积分的时候还不能光用普通的数值积分的方法，得牵涉到符号运算(就是mathematic里面做积分一样) |
|
m*****n
发帖数: 5245 | 13 ☆─────────────────────────────────────☆
ttgg (暂时没有昵称) 于 (Sat Aug 22 21:40:15 2009, 美东) 提到:
1。Java里如何比较两个objects是否相等
2。怎样找出一个list是否包含循环
3。inheritance和composition：什么时候需要用到哪种？
4。一个int array
如何找出subarray，使得元素之和最大
比如{-2,3,-1,3,-4}
那么答案应该是{3,-1,3}
☆─────────────────────────────────────☆
Macheda (Federico Macheda) 于 (Sat Aug 22 21:48:18 2009, 美东) 提到:
1. equal
2. 不同步长
3. inheritance is-a, composition has-a
4. 请问goodbug
☆─────────────────────────────────────☆
mitbbs59 (bEQi) 于 (Sat Aug 22 |
|
l*******r
发帖数: 511 | 14 for i=1 to n
maxendinghere=max(maxendinghere+x_i,0)
maxsofar=max(maxsofar,maxendinghere) |
|
c**********e
发帖数: 2007 | 15 The following code is from a book. But it does not work.
I have not been able to make it work. Anybody look at it?
________________________________
#include
#include
using namespace std;
int maxSub(int a[], int n, int& i, int& j) {
int t=a[0], vmax = a[0];
int tmin = min(0, t);
for(int k=1; k
{
t+=a[k];
if(t-tmin > vmax) { vmax = t-tmin; j=k; }
if(t < tmin) { tmin =t; i=(k+1
}
return vmax;
}
int main() { |
|
c**********e
发帖数: 2007 | 16 For binary search, after 2 steps (checking two points), the remaining
interval (or array length, etc) is 1/4 of the original one. But for
triple search, after 1 step (checking 2 points), the remaining interval
(or array length, etc) is 1/3 of the original one.
For an example, if an array a[1000] is sorted. You want to find
some i such that a[i]=35. For binary search, after first checking
a[500], then checking either a[250] or a[750], i is narrowed down
to a subarray of 250 integers. But for tri |
|
f**r
发帖数: 865 | 17 One final pass for the remaining numbers. Example:
a1 a2 a3 a4 a5 a6
b1 b2 b3 b4 b5 b6
=>
a1 b1 a3 b3 a5 b5
a2 b2 a4 b4 a6 b6
=>
a1 b1 a2 b2 a5 b5
a3 b3 a4 b4 a6 b6
Now we would like to switch (a5, b5) (incomplete) with (a3, b3, a4, b4).
Here, the problem is equivalent to left shift subarray {a5 b5 a3 b3 a4 b4}
by 2, another interview question that has an O(N) solution. :-)
作？ |
|
c***z
发帖数: 6348 | 18 It seems that it is better to store total # of 1's.
My idea is first fix column i and column j, try to find the max all 0
rectangular between them.
For that purpose, we need one pass on the rows, keeping track of the longest
rectangular ending at row k (LREK). This is a variant of the max sum
subarray problem.
If row k has an 1, then LREK=0; otherwise add 1 to the previous LREK.
To fast calculate if row k has an 1 or not, it is better to store the total
# of 1's and just do a subtraction.
O(M^2N |
|
x******3
发帖数: 245 | 19 可以用以下算法
1. sort the array // O(nlgn)
2. iterate through the array, for each element x, compute k = y - x, binary
search k in the rest of the array. if
found, return x and k; if not found, repeat step 2 on the subarray without x
// O(nlgn)
总时间复杂度O(nlgn), space O(1)
这道题应该是CLRS上的习题 |
|
p*****u
发帖数: 310 | 20 谢谢小尾羊. 不过题目2可转化成对每个元素乘-1后求最长连续子数组, 使得sum大于给
定数乘-1, 这就又归结为max sum
subarray, 复杂度O(n). |
|
g*******y
发帖数: 1930 | 21 小于等于给定数，大于等于给定数，是一回事
这个题跟max sum subarray的区别是，在sum满足一定条件下，找最长的子数组；
max sum问题是子数组和最大，完全不涉及到子数组的长度 |
|
j***n
发帖数: 301 | 22 来自主题: JobHunting版 - 总结一道题 有道题目最近频繁出现，特地总结一下常规解法以及它的变体。有个经典变体我还没看
到一个很经典的答案，希望有人补上，呵呵。
1. The largest rectangle under a histogram
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html
Given: An integer array represents a histogram
Goal: Find the largest rectangle under the histogram.
Key observation: 输入为一个整数数组。如果某元素比它两边的邻居都小（比如Ai)，
那么高度大于Ai的矩阵要么在该元素左边，要么在该元素右边，不可能穿过Ai。利用这
个性质，想办法遍历所有的矩形。
Complexity O(N) where N is the size of the given array.
2. Maximum subarray with all 1’s. (Generalization of problem 1)
http: |
|
l******h
发帖数: 405 | 23 这题我觉得有点像Max SubArray Sum问题，可以用O(n)做出来？ |
|
j**l
发帖数: 2911 | 24 有些类似，只是Max SubArray Sum有贪心的策略，一路向前走，不断更新舍弃。
这个题目用的是栈，有回溯的意味。不过每个元素最多入栈出栈一次，保证了O(n)的复
杂度。
这道题，其实更象编译原理课程中讲到的左右括号匹配，只是一个右括号，可以cancel
前面若干个左括号。 |
|
r********t
发帖数: 395 | 25 if all the elements are positive, easy;
but what can we do if negative numbers are possible?
is there any O(n) solution? |
|
b********h
发帖数: 119 | 26 how do you solve it in O(n) when all the elements are positive? |
|
r********t
发帖数: 395 | 27 从a【0】+a【1】....一直加下去，直到你的sum大于给定的sum
然后再用你的sum一个个从a【0】开始减。。。 |
|
r********t
发帖数: 395 | 28 不过这个不适用于负数，因为这个方法的一个特性就是sum是递增的。 |
|
r********t
发帖数: 395 | 29 不过这个不适用于负数，因为这个方法的一个特性就是sum是递增的。 |
|
b********h
发帖数: 119 | 30 I see. Then how about find the smallest number in the array, add this number
to every element of the array and to the sum you are looking for. It is the
same problem as before. |
|
l*****a
发帖数: 14598 | 31 what is the result to find 7 from "6 4 2 3" with your algorithm
i think at least u need the array to be sorted |
|
|
h**********d
发帖数: 4313 | 33 楼住的意思应该是subsequence，这个例子里没有 |
|
f***g
发帖数: 214 | 34 这个题，几天前讨论过，老帖找不到了
要用hashtable |
|
J*****u
发帖数: 30 | 35 用hashtable 的那个貌似是sum为0吧,但是这里sum不为0的,可正,可负. |
|
|
b********h
发帖数: 119 | 37 subsequence不是subarray吧。bruteforce应该是2^n。
DP的做法跟max subsequence一样，定义S(i)为在i结束的max increaseing sequence，
则，
S(i) = max{S(j)+A[i], A[i]>A[j] && 0<=j |
|
j**l
发帖数: 2911 | 38 是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解决。想了半天未果
，请帮忙解答，谢谢。 |
|
g*******y
发帖数: 1930 | 39 我觉得这个题就是那个max length of subarray which sum to a
target value的变种。因为这个题array是binary的(意味着一段子数组的和的变化是“
连续”的)，这个性质使得不需要经典题中用到的O(n)的hashtable |
|
i**r
发帖数: 40 | 40 Hmmm...
I was thinking the question was related to maxmium subarray problem or
subset sum problem. I was probably wrong.
The brutal force solution can achieve O(n^2) time complexity. To find an
O(n) solution, the problem need to be formulated as a recursion on a one-
dimensional subproblem space. I simply fail to see optimal substructures
among the prefix subproblems. Is it really possible to get an O(n) time
solution?
sum |
|
s***e
发帖数: 793 | 41 1L is right. You need to find the peak and search two subarray.
integers |
|
c******n
发帖数: 4965 | 42 必需得用，否则每merge 一个cell, 你要挪n 个cell,
用2个extra N-cell array 就行了，
treat a subsequence by jumping every other K elements, so you have K
subarrays
for each of the K-"sub array"s
merge_sort(sub_array, tmp_buffer ---> tmp-buffer2 )
switch the 2 tmp_buffers
finally you have the result in tmp_buffer2 |
|
x***y
发帖数: 633 | 43 old question, you can check 2D-Kadane algorithm... |
|
|
|
i***1
发帖数: 95 | 46 programming pearls 8.7.13 |
|
h**6
发帖数: 4160 | 47 任选两行作为上下边，有O(n^2)种方法，对于每一种情况，进行一维最大子数组处理，
复杂度为O(n)。
总复杂度为O(n^3)。 |
|
t****a
发帖数: 1212 | 48 But if the columns/rows in the sub-matrix is not adjacent? |
|
|
z****n
发帖数: 1379 | 50 sub-sequense还是subarray?
sub-sequense可以不连续的吧，那这题就没意义了
space
and |
|
