logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
一道老题
avatar
一道老题# JobHunting - 待字闺中
s*t
1 楼
Given an array of integers(both positive and negative) divide the array into
two parts(sub-arrays) such that the
difference between the sum of elements in each array is minimum????
avatar
c*e
2 楼
This should be simple bah.
Calculate the partial sum from 1 to i for each i.
Denote it as S[i]. S[n] is total sum.
Find the S[i] which is closest to S[n]/2 in absolute
value. Then the two arrays are a[1],...,a[i]
and a[i+1],...,a[n].
The complexity is O(n).
avatar
m*a
3 楼
你这个好像不对
一个反例：
{1，2，2，3}

【在 c**********e 的大作中提到】
: This should be simple bah.
: Calculate the partial sum from 1 to i for each i.
: Denote it as S[i]. S[n] is total sum.
: Find the S[i] which is closest to S[n]/2 in absolute
: value. Then the two arrays are a[1],...,a[i]
: and a[i+1],...,a[n].
: The complexity is O(n).
avatar
g*y
4 楼
bless lz get an onsite!
avatar
c*e
5 楼
if lz's "divide the array into two parts" means 1 to i and i+1 to n,
then my solution should be correct, even though not unique.
Is my understanding of the problem correct?

【在 m********a 的大作中提到】
: 你这个好像不对
: 一个反例：
: {1，2，2，3}
avatar
H*M
6 楼
bless 2!

【在 g*******y 的大作中提到】
: bless lz get an onsite!
avatar
m*a
7 楼
这个得问楼主，呵呵

【在 c**********e 的大作中提到】
: if lz's "divide the array into two parts" means 1 to i and i+1 to n,
: then my solution should be correct, even though not unique.
: Is my understanding of the problem correct?
avatar
r*o
8 楼
应该是说随机分成两半吧，顺序可能交错。
Bless~

【在 c**********e 的大作中提到】
: if lz's "divide the array into two parts" means 1 to i and i+1 to n,
: then my solution should be correct, even though not unique.
: Is my understanding of the problem correct?
avatar
v*t
9 楼
then it's NPC, can reduce to Partition NPC problem.

【在 r****o 的大作中提到】
: 应该是说随机分成两半吧，顺序可能交错。
: Bless~
avatar
v*t
10 楼
I remember some one proved this on the Programming Board several months ago.

【在 v*****t 的大作中提到】
: then it's NPC, can reduce to Partition NPC problem.
avatar
c*e
11 楼
I also feel if my understanding is correct, then the problem is too
simple (sometimes naive ... hehehehe).

【在 r****o 的大作中提到】
: 应该是说随机分成两半吧，顺序可能交错。
: Bless~
avatar
H*M
12 楼
不是你理解的那样了
肯定是元素随便拎的
如果都是正数，又有range的话，可以用DP解，

【在 c**********e 的大作中提到】
: I also feel if my understanding is correct, then the problem is too
: simple (sometimes naive ... hehehehe).
avatar
r*o
13 楼
用DP应该可以算出那个比较接近的两个和来，
但是怎么输出那些元素呢？

【在 H*M 的大作中提到】
: 不是你理解的那样了
: 肯定是元素随便拎的
: 如果都是正数，又有range的话，可以用DP解，
avatar
s*t
14 楼
DP的话， 最小 子问题是什么呢？

【在 H*M 的大作中提到】
: 不是你理解的那样了
: 肯定是元素随便拎的
: 如果都是正数，又有range的话，可以用DP解，
avatar
s*t
15 楼
谢谢小尾，也祝你早日拿到offer.

【在 g*******y 的大作中提到】
: bless lz get an onsite!
avatar
c*o
16 楼
bless~
avatar
g*u
17 楼
有负数也可以DP吧。range为所有负数的和，到所有正数的和
如果要记录是那些元素，space就要n*range了

【在 H*M 的大作中提到】
: 不是你理解的那样了
: 肯定是元素随便拎的
: 如果都是正数，又有range的话，可以用DP解，
avatar
r*o
18 楼
有谁用DP作出来这道题，并且能正确输出两组数吗？
我用DP发现有可能会取重复的数。

【在 H*M 的大作中提到】
: 不是你理解的那样了
: 肯定是元素随便拎的
: 如果都是正数，又有range的话，可以用DP解，
相关阅读
请问如何安全地reverse 一个integer应该隐瞒这段工作经历吗？OPT 已经开始了，但是没有收到EAD卡，现在可以申请H1B吗？去哪里找到社科类的工作申请经历？MS onsite 面经J2EE interview 问题（比较general...）刚刚开始上班，来了个offer明天要去onsite，公司给我联系并付了limo，我还用给小费么？H1B extenstion这题怎么做的？salary negotiation 一周无回音，对offer会有影响么？请教OPT申请费都是自己交钱吗？一道面试题帮忙看看这email是怎么回事儿on-site面经该不该离开当前公司？拿到了搬家费，很惊喜的发现发现公司给多了。OPT加急需要发到的传真号码是多少？帮老婆问个暑期实习的问题OPT跟H1B同时申请哪个更快？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。