b*****o
发帖数: 240 | 1 12个一组数据（有正有负），求组合求和最大值。要求：最少有4个数字（最多不限）相
加，但这组数字必须连续（如果取x1,x2, x4,x5,就不行，因为x3漏掉了。)
………………
比如这12个数字是：3， －2， 0， 1， －1， 2， 3， －4， －2， 4， －1， 3
可不可请给出算法（source code)与结果。多谢了。 |
s***t
发帖数: 113 | 2 Denote A[i][j] = \sum_{i<=k<=j}. Then check all A[i][j] so that j>=i+3 to find
the max. O(n^2) complexity.
相
【在 b*****o 的大作中提到】
: 12个一组数据（有正有负），求组合求和最大值。要求：最少有4个数字（最多不限）相
: 加，但这组数字必须连续（如果取x1,x2, x4,x5,就不行，因为x3漏掉了。)
: ………………
: 比如这12个数字是：3， －2， 0， 1， －1， 2， 3， －4， －2， 4， －1， 3
: 可不可请给出算法（source code)与结果。多谢了。
|
t*s
发帖数: 1504 | 3 俺想到一种线性地。。。
find
【在 s***t 的大作中提到】
: Denote A[i][j] = \sum_{i<=k<=j}. Then check all A[i][j] so that j>=i+3 to find
: the max. O(n^2) complexity.
:
: 相
|
s***t
发帖数: 113 | 4 how is your alg going? O(N) seems a little challenging for me.
【在 t*s 的大作中提到】
: 俺想到一种线性地。。。
:
: find
|
t*s
发帖数: 1504 | 5 A[i] i=1 to n-3 代表以第i个数字开头的串的最大值
V[i] i=1 to n 代表第i个的值
A[n-3]=V[n-3]+V[n-2]+V[n-1]+V[n] 一种可能
A[n-4]=max { V[n-4]+V[n-3]+V[n-2]+V[n-1], V[n-4]+A[n-3] }
A[n-5]到A[1]依此可得
相
【在 b*****o 的大作中提到】
: 12个一组数据（有正有负），求组合求和最大值。要求：最少有4个数字（最多不限）相
: 加，但这组数字必须连续（如果取x1,x2, x4,x5,就不行，因为x3漏掉了。)
: ………………
: 比如这12个数字是：3， －2， 0， 1， －1， 2， 3， －4， －2， 4， －1， 3
: 可不可请给出算法（source code)与结果。多谢了。
|
s***e
发帖数: 284 | 6 最好的那个子串一定以正数开始
而且前面的串之和一定小于0
【在 s***t 的大作中提到】
: how is your alg going? O(N) seems a little challenging for me.
|
s***t
发帖数: 113 | 7 sounds good.
【在 t*s 的大作中提到】
: A[i] i=1 to n-3 代表以第i个数字开头的串的最大值
: V[i] i=1 to n 代表第i个的值
: A[n-3]=V[n-3]+V[n-2]+V[n-1]+V[n] 一种可能
: A[n-4]=max { V[n-4]+V[n-3]+V[n-2]+V[n-1], V[n-4]+A[n-3] }
: A[n-5]到A[1]依此可得
:
: 相
|
s***e
发帖数: 284 | 8 没写清楚啊
A[n-5]到底怎么算？
【在 t*s 的大作中提到】
: A[i] i=1 to n-3 代表以第i个数字开头的串的最大值
: V[i] i=1 to n 代表第i个的值
: A[n-3]=V[n-3]+V[n-2]+V[n-1]+V[n] 一种可能
: A[n-4]=max { V[n-4]+V[n-3]+V[n-2]+V[n-1], V[n-4]+A[n-3] }
: A[n-5]到A[1]依此可得
:
: 相
|
t*s
发帖数: 1504 | 9 A[n-5]=max { V[n-5]+V[n-4]+V[n-3]+V[n-2], V[n-5]+A[n-4] }
没写清楚啊
A[n-5]到底怎么算？
【在 s***e 的大作中提到】
: 没写清楚啊
: A[n-5]到底怎么算？
|
h****t
发帖数: 93 | 10 <>上有类似问题，最优解是线性的.
相
【在 b*****o 的大作中提到】
: 12个一组数据（有正有负），求组合求和最大值。要求：最少有4个数字（最多不限）相
: 加，但这组数字必须连续（如果取x1,x2, x4,x5,就不行，因为x3漏掉了。)
: ………………
: 比如这12个数字是：3， －2， 0， 1， －1， 2， 3， －4， －2， 4， －1， 3
: 可不可请给出算法（source code)与结果。多谢了。
|
|
|
P*****f
发帖数: 2272 | 11 it's linear. The problem without the constraints that at least consisting of 4
was one problem in our final.
The idea is define the maximium sequence ends/starts at each elements. Then
evaluate both the signs of next element and the privous sequence to grow the
problem size
【在 h****t 的大作中提到】
: <>上有类似问题，最优解是线性的.
:
: 相
|
b*****o
发帖数: 240 | 12 （首先谢谢前几位的智慧襄助）
12个一组数据（有正有负），可分割成几块（不可重复分割），但要求：最少有4个数字
（最多不限）一组，但这组数字必须连续（如果取x1,x2, x4,x5,就不行，因为x3漏掉了
。)
…………
注意，各组之间可以舍弃一些数（例如第一组数选中x1,x2,x3,x4; 第二组数选中x7,x8,
x9,x10,x11)
求：哪种分割法时，各组数相加指最大。最终求此最大值。
假设这12个数字全是正的，那其组合就是本12个数，最大值就是这12个数的和。
比如这12个数字是：3， －2， 0， 1， －1， 2， 3， －4， －2， 4， －1， 3
可不可请给出算法（source code)与结果。多谢了。 |
t*s
发帖数: 1504 | 13 i think it's still linear
字
了
,
【在 b*****o 的大作中提到】
: （首先谢谢前几位的智慧襄助）
: 12个一组数据（有正有负），可分割成几块（不可重复分割），但要求：最少有4个数字
: （最多不限）一组，但这组数字必须连续（如果取x1,x2, x4,x5,就不行，因为x3漏掉了
: 。)
: …………
: 注意，各组之间可以舍弃一些数（例如第一组数选中x1,x2,x3,x4; 第二组数选中x7,x8,
: x9,x10,x11)
: 求：哪种分割法时，各组数相加指最大。最终求此最大值。
: 假设这12个数字全是正的，那其组合就是本12个数，最大值就是这12个数的和。
: 比如这12个数字是：3， －2， 0， 1， －1， 2， 3， －4， －2， 4， －1， 3
|
b*****o
发帖数: 240 | 14 可以给些具体点的吗？谢了
【在 t*s 的大作中提到】
: i think it's still linear
:
: 字
: 了
: ,
|
t*s
发帖数: 1504 | 15 A[i]还是表示从i开始的最大值
A[n]到A[n-2]都是不可能
A[n-3]一种可能
...
A[n-k]=max{ 接下来4个+A[n-k+4], 接下来5个+A[n-k+5],接下来6个＋A[n-k+6],接下来7
个＋A[n-k+7] } //8个以上的不用考虑了，可以拆成两段看
最后找到最大的A
【在 b*****o 的大作中提到】
: 可以给些具体点的吗？谢了
|
b*****o
发帖数: 240 | 16 it is not clear yet.....
I am not looking for one A. I am looking for max of the sum of multiple A.
Within each A, there should be 4 or more consecutive numbers. and no overlap
between different A. Do you have any idea? Thanks.
来7
【在 t*s 的大作中提到】
: A[i]还是表示从i开始的最大值
: A[n]到A[n-2]都是不可能
: A[n-3]一种可能
: ...
: A[n-k]=max{ 接下来4个+A[n-k+4], 接下来5个+A[n-k+5],接下来6个＋A[n-k+6],接下来7
: 个＋A[n-k+7] } //8个以上的不用考虑了，可以拆成两段看
: 最后找到最大的A
|
t*s
发帖数: 1504 | 17 我就是这个意思
【在 b*****o 的大作中提到】
: it is not clear yet.....
: I am not looking for one A. I am looking for max of the sum of multiple A.
: Within each A, there should be 4 or more consecutive numbers. and no overlap
: between different A. Do you have any idea? Thanks.
:
: 来7
|
r****c
发帖数: 2585 | 18 第一个问题的time complexity is linear, and space complexity is O(1)
只给一个简单可以理解的solution,
1. 先考虑所有长度为四的连续数字,找出最大的一个,一共需要linear time and O(1)
space. Let max be the sum of the max solution.
2. 考虑长度为四以上的数字,如果是最大,头和尾一定是正数. 从第一个正数开始linear
scan
a) assume first positive is A[i], consider x = A[i]+A[i+1]+A[i+2]+A[i+3]+A[i+4
], j=A+5
if it is negative then begin from A[j] and find first positive one.
b) If x is positive, then iteratively add x=x+A[j] until x become negative. In
this process,
if x > max, then se
【在 t*s 的大作中提到】
: 我就是这个意思
|
t*s
发帖数: 1504 | 19 your algorithm is wrong
see: 1 -inf 1 1 1 1 1
linear
+4
In
【在 r****c 的大作中提到】
: 第一个问题的time complexity is linear, and space complexity is O(1)
: 只给一个简单可以理解的solution,
: 1. 先考虑所有长度为四的连续数字,找出最大的一个,一共需要linear time and O(1)
: space. Let max be the sum of the max solution.
: 2. 考虑长度为四以上的数字,如果是最大,头和尾一定是正数. 从第一个正数开始linear
: scan
: a) assume first positive is A[i], consider x = A[i]+A[i+1]+A[i+2]+A[i+3]+A[i+4
: ], j=A+5
: if it is negative then begin from A[j] and find first positive one.
: b) If x is positive, then iteratively add x=x+A[j] until x become negative. In
|
r****c
发帖数: 2585 | 20 Just for negative not begin from A[j], begin from
the first number that is A[i+1]
j=i+5 should put in b).
Actually the linear scan is enough, the basic idea
should be there.
【在 t*s 的大作中提到】
: your algorithm is wrong
: see: 1 -inf 1 1 1 1 1
:
: linear
: +4
: In
|
r****c
发帖数: 2585 | 21 the key idea is that if it is greater than length 8,
it can decomposed into several small chunks such that
every chunks with length smaller than 8,
the output keeps the same. |
