# 如何快速找到使得值最大的点？请提供Java或C++代码。

go评论64阅读模式

How to find the point that gives the maximum value fast? Java or c++ code please

# 问题

``````int[][] data = new int[][]{
{1, 1},
{3, 3},
{2, 4}};
``````

``````x 轴: -2 -1 0 1 2 3 4 5 6 7
1 1:       1 2 1
3 3:       1 2 3 4 3 2 1
2 4:  1  2 3 4 5 4 3 2 1
``````

(Note: The translation above provides the information related to your code and the problem statement without repeating the question.)

I need a fast way to find maximum value when intervals are overlapping, unlike finding the point where got overlap the most, there is "order". I would have `int[][] data` that 2 values in `int[]`, where the first number is the center, the second number is the radius, the closer to the center, the larger the value at that point is going to be. For example, if I am given data like:

``````int[][] data = new int[][]{
{1, 1},
{3, 3},
{2, 4}};
``````

Then on a number line, this is how it's going to looks like:

``````x axis: -2 -1 0 1 2 3 4 5 6 7
1 1:       1 2 1
3 3:       1 2 3 4 3 2 1
2 4:  1  2 3 4 5 4 3 2 1
``````

So for the value of my point to be as large as possible, I need to pick the point x = 2, which gives a total value of 1 + 3 + 5 = 9, the largest possible value. It there a way to do it fast? Like time complexity of O(n) or O(nlogn)

# 答案1

``````intervals = [(1,1), (3,3), (2,4)]

events = []
for mid, width in intervals:
before_start = mid - width - 1
at_end = mid + width
events += [(before_start, 1), (mid, -2), (at_end, 1)]

events.sort()

prev_x = -1000
v = 0
dv = 0

best_v = -1000
best_x = None

for x, change in events:
dx = x - prev_x
v += dv * dx
if v > best_v:
best_v = v
best_x = x
dv += change
prev_x = x

print best_x, best_v
``````

``````TreeMap<Integer, Integer> ts = new TreeMap<Integer, Integer>();

for (int i = 0; i < cows.size(); i++) {
int index = cows.get(i)[0] - cows.get(i)[1];
if (ts.containsKey(index)) {
ts.replace(index, ts.get(index) + 1);
} else {
ts.put(index, 1);
}

index = cows.get(i)[0] + 1;
if (ts.containsKey(index)) {
ts.replace(index, ts.get(index) - 2);
} else {
ts.put(index, -2);
}

index = cows.get(i)[0] + cows.get(i)[1] + 2;
if (ts.containsKey(index)) {
ts.replace(index, ts.get(index) + 1);
} else {
ts.put(index, 1);
}
}

int value = 0;
int best = 0;
int change = 0;
int indexBefore = -100000000;

while (ts.size() > 1) {
int index = ts.firstKey();
value += (ts.get(index) - indexBefore) * change;
best = Math.max(value, best);
change += ts.get(index);
ts.remove(index);
}
``````

This can be done with a simple O(n log n) algorithm.

Consider the value function v(x), and then consider its discrete derivative dv(x)=v(x)-v(x-1). Suppose you only have one interval, say `{3,3}`. dv(x) is 0 from -infinity to -1, then 1 from 0 to 3, then -1 from 4 to 6, then 0 from 7 to infinity. That is, the derivative changes by 1 "just after" -1, by -2 just after 3, and by 1 just after 6.

For n intervals, there are 3*n derivative changes (some of which may occur at the same point). So find the list of all derivative changes `(x,change)`, sort them by their x, and then just iterate through the set.

Behold:

``````intervals = [(1,1), (3,3), (2,4)]

events = []
for mid, width in intervals:
before_start = mid - width - 1
at_end = mid + width
events += [(before_start, 1), (mid, -2), (at_end, 1)]

events.sort()

prev_x = -1000
v = 0
dv = 0

best_v = -1000
best_x = None

for x, change in events:
dx = x - prev_x
v += dv * dx
if v &gt; best_v:
best_v = v
best_x = x
dv += change
prev_x = x

print best_x, best_v
``````

And also the java code:

`````` TreeMap&lt;Integer, Integer&gt; ts = new TreeMap&lt;Integer, Integer&gt;();

for(int i = 0;i&lt;cows.size();i++) {
int index = cows.get(i)[0] - cows.get(i)[1];
if(ts.containsKey(index)) {
ts.replace(index, ts.get(index) + 1);
}else {
ts.put(index, 1);
}

index = cows.get(i)[0] + 1;
if(ts.containsKey(index)) {
ts.replace(index, ts.get(index) - 2);
}else {
ts.put(index, -2);
}

index = cows.get(i)[0] + cows.get(i)[1] + 2;
if(ts.containsKey(index)) {
ts.replace(index, ts.get(index) + 1);
}else {
ts.put(index, 1);
}
}

int value = 0;
int best = 0;
int change = 0;
int indexBefore = -100000000;

while(ts.size() &gt; 1) {
int index = ts.firstKey();
value += (ts.get(index) - indexBefore) * change;
best = Math.max(value, best);
change += ts.get(index);
ts.remove(index);
}
``````

where `cows` is the data

# 答案2

• 一个三角形的顶点
• 两个三角形相交的交点，或者是两个三角形的整体交点。多个三角形意味着更多可能的交点，不幸的是，可能的交点数量呈二次增长，所以使用这种方法可能无法达到`O(N log N)`或更好的时间复杂度（除非找到一些良好的优化方法），除非交点的数量是`O(N)`或更少。

Hmmm, a general `O(n log n)` or better would be tricky, probably solvable via linear programming, but that can get rather complex.

After a bit of wrangling, I think this can be solved via line intersections and summation of function (represented by line segment intersections). Basically, think of each as a triangle on top of a line. If the inputs are `(C,R)` The triangle is centered on `C` and has a radius of `R`. The points on the line are `C-R (value 0)`, `C (value R)` and `C+R (value 0)`. Each line segment of the triangle represents a value.

Consider any 2 such "triangles", the max value occurs in one of 2 places:

• The peak of one of the triangle
• The intersection point of the triangles or the point where the two triangles overall. Multiple triangles just mean more possible intersection points, sadly the number of possible intersections grows quadratically, so `O(N log N)` or better may be impossible with this method (unless some good optimizations are found), unless the number of intersections is `O(N)` or less.

To find all the intersection points, we can just use a standard algorithm for that, but we need to modify things in one specific way. We need to add a line that extends from each peak high enough so it would be higher than any line, so basically from (C,C) to `(C,Max_R)`. We then run the algorithm, output sensitive intersection finding algorithms are `O(N log N + k)` where `k` is the number of intersections. Sadly this can be as high as `O(N^2)` (consider the case `(1,100), (2,100),(3,100)...` and so on to `(50,100)`. Every line would intersect with every other line. Once you have the `O(N + K)` intersections. At every intersection, you can calculate the the value by summing the of all points within the queue. The running sum can be kept as a cached value so it only changes `O(K)` times, though that might not be posible, in which case it would `O(N*K)` instead. Making it it potentially `O(N^3)` (in the worst case for `K`) instead :(. Though that seems reasonable. For each intersection you need to sum up to `O(N)` lines to get the value for that point, though in practice, it would likely be better performance.

There are optimizations that could be done considering that you aim for the max and not just to find intersections. There are likely intersections not worth pursuing, however, I could also see a situation where it is so close you can't cut it down. Reminds me of convex hull. In many cases you can easily reduce 90% of the data, but there are cases where you see the worst case results (every point or almost every point is a hull point). For example, in practice there are certainly causes where you can be sure that the sum is going to be less than the current known max value.

Another optimization might be building an interval tree.

• 本文由 发表于 2020年10月2日 09:29:34
• 转载请务必保留本文链接：https://go.coder-hub.com/64165156.html
• c++
• geometry
• java
• linear-programming
• math

go 70

go 59

go 55

go 55