k***e
发帖数: 556 | 1 input: a circular array
output: a subvector of the array that has max sum
可以想象排列在圆周上的n个元素，求连续的k个使得其和最大
我的想法是
1. take any element as the leader and break the circle into one dimensional
array a[1:n]. use the classical method to get the maxsum subvector
2. we did not consider the case that the maxsum subvector in the circle
passes a[1]. in the next step we will figure out the maxsum subvector that
passes a[1], suppose it is a[n - i:j].
3. claim: a[j+1:n-i-1] is the minsum subvector of a[1:n]. beca | w********p
发帖数: 948 | 2 额觉得， 这道题的关键不是array is circle or not. 因为我们只能用array来表达
circle array. circle array 只是多了几步边界问题。
搂主提到的“classical method to get the maxsum subvector“， 不知道running
time 是多少。
我的方法是 土土的将相临的K个数加起来。包括circle的情况。时间是 O(K*N)， 空间
是O（N)
不知道，有没有人更好的方法
dynamic 在这道题中应该用不着吧。 | g*******y
发帖数: 1930 | 3 1.K是一个任意的数
2.不管K是固定的，还是任意的，都只要O(N)
【在 w********p 的大作中提到】
: 额觉得， 这道题的关键不是array is circle or not. 因为我们只能用array来表达
: circle array. circle array 只是多了几步边界问题。
: 搂主提到的“classical method to get the maxsum subvector“， 不知道running
: time 是多少。
: 我的方法是 土土的将相临的K个数加起来。包括circle的情况。时间是 O(K*N)， 空间
: 是O（N)
: 不知道，有没有人更好的方法
: dynamic 在这道题中应该用不着吧。
| w********p
发帖数: 948 | 4 根据你提供的algorithm and feedback, 从写思路. one time scan
running time O(n) space O(1)
Please correct me, if logic error
//n is the array size
maxSum=-99999999;
if (k>n) return failed
for (int i=0; i
startIndex=i;
endIndex= (i+k-1)% n;
//get the sum of k number from startIndex to endIndex
sum=SumKMember(startIndex, endIndex， sum);
if (sum>maxSum ) { maxSum = sum; retrunIndex=startIndex }
}
//get sum only one time scan
int SumKMember(int startIndex, int endIndex, sum) {
【在 k***e 的大作中提到】
: input: a circular array
: output: a subvector of the array that has max sum
: 可以想象排列在圆周上的n个元素，求连续的k个使得其和最大
: 我的想法是
: 1. take any element as the leader and break the circle into one dimensional
: array a[1:n]. use the classical method to get the maxsum subvector
: 2. we did not consider the case that the maxsum subvector in the circle
: passes a[1]. in the next step we will figure out the maxsum subvector that
: passes a[1], suppose it is a[n - i:j].
: 3. claim: a[j+1:n-i-1] is the minsum subvector of a[1:n]. beca
| H*M
发帖数: 1268 | 5 呼吁geniusxsy出手
刚实现了下,发现远比我想象的要难.
在classical 非circular array的那个问题上改的
但是复杂了许多.还出错....
please test: 1 2 4 -3 5 2
should return 14, not 11.
【在 g*******y 的大作中提到】
: 1.K是一个任意的数
: 2.不管K是固定的，还是任意的，都只要O(N)
| l*******r
发帖数: 511 | 6 duplicate the array
【在 H*M 的大作中提到】
: 呼吁geniusxsy出手
: 刚实现了下,发现远比我想象的要难.
: 在classical 非circular array的那个问题上改的
: 但是复杂了许多.还出错....
: please test: 1 2 4 -3 5 2
: should return 14, not 11.
| H*M
发帖数: 1268 | 7 没用的
我的思想就是duplicate the array
你implement看看就知道了
【在 l*******r 的大作中提到】
: duplicate the array
| w********p
发帖数: 948 | 8 code is here, I run it simply, it looks good
O(n) for running time, and O(1) for space
#include
#include
#include
using namespace std;
int SumKMember(int iArray[],int startIndex, int endIndex, int sum);
int main (int argc, char *args[]) {
if (argc != 2) {
cout<<"comment line: a.exe number\n";
return 0;
}
int k=atoi(args[1]);
//n is the array size
int maxSum=-99999999;
int iArray[] = {1, 2 , 4 , -3, 5 ,2};
int n = sizeof( iArray) /sizeof | g*******y
发帖数: 1930 | 9 这题的题意应该是，找一段长度任意的子数组使得和最大，k不是一个给定的参数。
【在 w********p 的大作中提到】
: code is here, I run it simply, it looks good
: O(n) for running time, and O(1) for space
: #include
: #include
: #include
: using namespace std;
: int SumKMember(int iArray[],int startIndex, int endIndex, int sum);
: int main (int argc, char *args[]) {
: if (argc != 2) {
: cout<<"comment line: a.exe number\n";
| l***i
发帖数: 632 | 10 enn...Your solution is correct.
dimensional
[j
【在 k***e 的大作中提到】
: input: a circular array
: output: a subvector of the array that has max sum
: 可以想象排列在圆周上的n个元素，求连续的k个使得其和最大
: 我的想法是
: 1. take any element as the leader and break the circle into one dimensional
: array a[1:n]. use the classical method to get the maxsum subvector
: 2. we did not consider the case that the maxsum subvector in the circle
: passes a[1]. in the next step we will figure out the maxsum subvector that
: passes a[1], suppose it is a[n - i:j].
: 3. claim: a[j+1:n-i-1] is the minsum subvector of a[1:n]. beca
| | | l***i
发帖数: 632 | 11
dynamic programming...in linear time
【在 w********p 的大作中提到】
: code is here, I run it simply, it looks good
: O(n) for running time, and O(1) for space
: #include
: #include
: #include
: using namespace std;
: int SumKMember(int iArray[],int startIndex, int endIndex, int sum);
: int main (int argc, char *args[]) {
: if (argc != 2) {
: cout<<"comment line: a.exe number\n";
| w********p
发帖数: 948 | 12 这要是我的面试题， 就这样fail了。 ：（
【在 g*******y 的大作中提到】
: 这题的题意应该是，找一段长度任意的子数组使得和最大，k不是一个给定的参数。
| H*M
发帖数: 1268 | 13 有O(1) space的
我说的是非circular
【在 l***i 的大作中提到】
:
: dynamic programming...in linear time
| g*******y
发帖数: 1930 | 14 呵呵，不是你的错，怪krone转述的题目误导你了，呵呵
【在 w********p 的大作中提到】
: 这要是我的面试题， 就这样fail了。 ：（
| H*M
发帖数: 1268 | 15 不过可以考虑设定k, 另外一道面试题
呵呵
【在 g*******y 的大作中提到】
: 呵呵，不是你的错，怪krone转述的题目误导你了，呵呵
| m*****f
发帖数: 1243 | 16 那数组里应该还有负数， 要不然和最大得数组当然是长度=n...
这个题总体来说题意不太清楚, 一般如果面试题要考虑负数的话， 肯定会说明
【在 g*******y 的大作中提到】
: 这题的题意应该是，找一段长度任意的子数组使得和最大，k不是一个给定的参数。
| m*****f
发帖数: 1243 | 17 设定k求最大连续和? 那不是太容易了吗?
【在 H*M 的大作中提到】
: 不过可以考虑设定k, 另外一道面试题
: 呵呵
| l***i
发帖数: 632 | 18 ...the standard dynamic programming can be implemented with O(1) extra space
...
The equation is
f(i) = max(a_i, f(i-1)+a_i)...
Hence at any time you need only f(i-1)...
【在 H*M 的大作中提到】
: 有O(1) space的
: 我说的是非circular
| H*M
发帖数: 1268 | 19 ok,we are talking about the same thing
usually when we talk about DP, i am thinking of extra space
space | H*M
发帖数: 1268 | 20 请5分钟内写对 :)
【在 m*****f 的大作中提到】
: 设定k求最大连续和? 那不是太容易了吗?
| | | H*M
发帖数: 1268 | 21 原楼主的方法好像是对的
现算一个maxconsum,再算minconsum（对非circular）,再用sum-minconsum,比谁大
没想到有什么不妥的地方。 好像也能用同样的方法算minconsum..
【在 l***i 的大作中提到】
: enn...Your solution is correct.
:
: dimensional
: [j
| w********p
发帖数: 948 | 22 俺嘬觉得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 | 23 我觉得楼主本来的idea就很好
至少我还没看出破绽
,
4
【在 w********p 的大作中提到】
: 俺嘬觉得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
| w********p
发帖数: 948 | 24 高度同意
我只是在丢脸后，试图找点回来
【在 H*M 的大作中提到】
: 我觉得楼主本来的idea就很好
: 至少我还没看出破绽
:
: ,
: 4
| H*M
发帖数: 1268 | 25 mm不要自责
前进让梦更近
-Toyota
【在 w********p 的大作中提到】
: 高度同意
: 我只是在丢脸后，试图找点回来
| k***e
发帖数: 556 | 26 晕 我贴了很长时间没人理
有mm（或貌似mm id）的回帖就立马一堆人回
看来弄个马甲很有必要
ps，我以为人人都知道给定 one dim array，找连续的sub array使得和最大
：）因为在programming pearl和许多算法课的作业里出现过
结果。。。
再次推荐没有读过 变成珍珠 读下这本书
【在 w********p 的大作中提到】
: 高度同意
: 我只是在丢脸后，试图找点回来
| s*x
发帖数: 3328 | 27 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 的大作中提到】
: ...the standard dynamic programming can be implemented with O(1) extra space
: ...
: The equation is
: f(i) = max(a_i, f(i-1)+a_i)...
: Hence at any time you need only f(i-1)...
| l***i
发帖数: 632 | 28
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.
..
【在 s*x 的大作中提到】
: 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 | 29 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...
【在 H*M 的大作中提到】
: 原楼主的方法好像是对的
: 现算一个maxconsum,再算minconsum（对非circular）,再用sum-minconsum,比谁大
: 没想到有什么不妥的地方。 好像也能用同样的方法算minconsum..
|
|
