f******n
发帖数: 279 | 1 问一道面试题：
int array a[n] with all element 0<=a[i]<=1000,find the subarray with
the largest sum that is <= max and output the starting and ending index of
this subarray and the sum. If there is more than one such subarray ,
output the one with smallest starting index.
请问这个算最快？ |
i**********e
发帖数: 1145 | |
f******n
发帖数: 279 | 3 能不能具体说下，看了半天也没看出头绪
谢谢了
【在 i**********e 的大作中提到】
: 请参考这里的讨论，O(N log N)，a table + binary search:
: http://www.mitbbs.com/article_t/JobHunting/31791913.html
|
h*********n
发帖数: 11319 | 4 how can you remember so many problems...
【在 i**********e 的大作中提到】
: 请参考这里的讨论，O(N log N)，a table + binary search:
: http://www.mitbbs.com/article_t/JobHunting/31791913.html
|
g******0
发帖数: 221 | 5 for the subsequence, does it have to be contiguous?
【在 f******n 的大作中提到】
: 问一道面试题：
: int array a[n] with all element 0<=a[i]<=1000,find the subarray with
: the largest sum that is <= max and output the starting and ending index of
: this subarray and the sum. If there is more than one such subarray ,
: output the one with smallest starting index.
: 请问这个算最快？
|
f******n
发帖数: 279 | 6 SOrry, the problem should be subarray insteady of subsequence.
【在 h*********n 的大作中提到】
: how can you remember so many problems...
|
i**********e
发帖数: 1145 | 7 这里我已经给出完整代码了（不过那题是 largest subarray sum >= max，思路是一样
的，代码作稍微修改就行）：
http://www.mitbbs.com/article/JobHunting/31797225_0.html
基本思路就是先建立一个 cumulative sum array, where C[i] = Sum[0..i]
这是因为方便取出任何一个 subarray sum，例如 Sum[i..j] = C[j] - C[i-1].
(这里你要小心 Sum[0..0] 无法算出，一个简单解决方法是定义 C 为 size N+1.)
然后呢，对 C[] 排序。这时候你应该知道为什么 C 也应该保有原有的对应 index，因
为排序会导致之前的对应 index 都没法找回了。
排好序呢，就对 C 的每个置作循环。For each C[i], apply binary search to find
its corresponding j which satisfy the condition:
XXXXX
这个是这个题目的关键，至于怎样我懒得解释了，那个原贴已经解释的非常清楚。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f******n 的大作中提到】
: 能不能具体说下，看了半天也没看出头绪
: 谢谢了
|
h*********n
发帖数: 11319 | 8 这题比那题简单，因为都是正数
一遍scan就行了。
void scan(int A[], int n, int k){
int sum = 0;
int maxSum = 0;
int start = -1;
int end = -1;
int j=0;
while ((sum+A[j]) <= k && j
sum += A[j];
j++;
}
start = 0;
end = j-1;
maxSum = sum;
int i=0;
while(j
sum -= A[i];
while((sum+A[j]) <=k && j
sum+=A[j];
j++;
}
i++;
if (sum > maxSum){
maxSum = sum;
start = i;
end = j-1;
}
}
cout<
}
find
【在 i**********e 的大作中提到】
: 这里我已经给出完整代码了（不过那题是 largest subarray sum >= max，思路是一样
: 的，代码作稍微修改就行）：
: http://www.mitbbs.com/article/JobHunting/31797225_0.html
: 基本思路就是先建立一个 cumulative sum array, where C[i] = Sum[0..i]
: 这是因为方便取出任何一个 subarray sum，例如 Sum[i..j] = C[j] - C[i-1].
: (这里你要小心 Sum[0..0] 无法算出，一个简单解决方法是定义 C 为 size N+1.)
: 然后呢，对 C[] 排序。这时候你应该知道为什么 C 也应该保有原有的对应 index，因
: 为排序会导致之前的对应 index 都没法找回了。
: 排好序呢，就对 C 的每个置作循环。For each C[i], apply binary search to find
: its corresponding j which satisfy the condition:
|
d*******l
发帖数: 338 | 9 我也想问这个问题。。
不过这题确实远比那题简单，就像你说的，O(n)就能出来，那题我看了半天才明白点意
思。。
【在 h*********n 的大作中提到】
: how can you remember so many problems...
|
s*****y
发帖数: 897 | 10 原文里面你提到你需要Max_index 和MIn_index，但是为什么最后你的code只有Max_
index呢，还在研究你的Code ing。。。。
【在 i**********e 的大作中提到】
: 请参考这里的讨论，O(N log N)，a table + binary search:
: http://www.mitbbs.com/article_t/JobHunting/31791913.html
|
