似乎现在的解法都不太完美。
ihasleetcode 的算法有点诡异。
Using binary search, we found the smallest j that satisfies the condition
sorted_cum[i]+k >= sorted_cum[j]
这里 为什么用这个不等式sorted_cum[i]+k >= sorted_cum[j]
使你打错了造成了我们的误解吗？
假设i〉j s[i]-s[j]>=k 才是我们要的， 还是 这里有什么深意呢？求解释？
然后你是要找刚好满足条件的，这个binary search 似乎不能保证找的的是刚好满足条
件的临界位置，只能保证满足条件，所以这里要找到刚好满足条件的那个按你的算法似
乎还是要n*n。
然后
你这里的
min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10}
的实际物理意义是当前sorted cum array 当前对应的坐标后的元素中的原始坐标的最
小值与最大值是谁？
如此设计不知意义何在？
不太明白，求解答。
觉得要设计应该设计成
min index 对应当前坐标前面到当前坐标中原始坐标的最小值，包括当前坐标
max index 对应当前坐标后面中原始坐标的最大值，也包括当前坐标。
虽然两者都考虑当前元素的原始坐标，但是显然是不会重复的。
然后当我们找到 一个i 对应的前面的满足不等式的临界值的时候，我们该做的就是直
接用对应的max index-min index 就能得到最大的range
还请ihasleetcode 能再详细谈谈
信人: ihasleetcode (1337coder), 信区: JobHunting
标 题: Re: 刚电面完，分享两个题目
发信站: BBS 未名空间站 (Wed Feb 16 03:13:53 2011, 美东)
Your ideas are mostly right, however you missed one important observation.
To
determine the largest range, the max_index array (not just the min_index
array) is needed too.
I give an example:
A[] = {5, -3, 2, -2, 1, 4, -3, -5, 6, 4, -2}
cum[] = {5, 2, 4, 2, 3, 7, 4, -1, 5, 9, 7}
sorted_cum[] = {-1, 2, 2, 3, 4, 4, 5, 5, 7, 7, 9}
orig_index[] = {8, 2, 4, 5, 3, 7, 1, 9, 6, 11, 10}
min_index[] = {1, 1, 1, 1, 1, 1, 1, 6, 6, 10, 10}
max_index[] = {11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 10}
Assume k = 5.
We start at i = 1, where the current element = -1. We skip this to i=2 for
illustrative purpose.
For i = 2, the current element = 2.
Using binary search, we found the smallest j that satisfies the condition
sorted_cum[i]+k >= sorted_cum[j] is j = 9. For j >= 9, we know that the
smallest index is min_index[9] = 6, and the largest index is max_index[9] =
11. Therefore, no doubt the maximum range when i = 2 must be 11 - 2 = 7.
Clearly, we need the max_index array as well.
Formally, the max range for sorted_cum[i] could be expressed in the
following equation:
max_range[i] = max(max_index[j], orig_index[i]) - min(min_index[j], orig_
index[i])
Then, the answer could be found as:
max(max_range[i]), for all i's.
解法2
下面的括号没打对，明天再仔细研究下
似乎应该可以实现nlogn
发信人: Jianna (jin), 信区: JobHunting
标 题: Re: 刚电面完，分享两个题目
发信站: BBS 未名空间站 (Thu Feb 17 16:07:54 2011, 美东)
Based on ibread's method, I think this is easy to understand, welcome any
comments.
Example: [-2, 2, -1, 3, -6] and k=3
For step 2
1) 还是计算sum[i]。O(n) sum_origianl=(-2,0,-1,2,-4)
2)排序，排的时候以sum[i]为key，同时带上下标i。O(nlgn)
sum=[(-4, 4), (-2, 0), (-1, 2), (0, 1), (2 ,3)]
3)给排好序的 arrary, every i , sum[i]-k; O(n)
(in order to在排序好的sum数组中找 sum[j] 正好 <= sum[i]-k, so I create a
sumnew)
Sumnew=[(-7,4),(-5,0),(-4,2),(-3,1),(-1,3)], next step is 在sum中找 最小下
标。
4)找min-index[i]. O(n)
a=0, b=0;
Temp=n+1; (put the temp min-index, set a value>n at first)
While(aif(sumnew[a].value>=sum[b].value){
If(temp>sum[b].xiabiao) temp= sum[b].xiabiao;
b++;
}
else {
min-index[sunnew[a].xiabiao]= temp;
a++ ;
}
}//end while
So, min-index[4]=5;min-index[0]=5; min-index[2]=4;min-index[1]=4; min-index
[3]=0
5) find biggest (i-min-index[i])
