这是数组A由N个正整数。有 N×(N + 1)/ 2
数组中的一个非空的连续子阵。
我们要计数的最大元素present在所有连续的子阵列。
例如:
An array A consisting of N positive integers. There are N × (N+1) / 2
non-empty continuous subarrays of the array A .
We have to Count the maximum element present in all continuous subarrays.
For Example:
1 2 3
Subarray List :
[1]
[2]
[3]
[1,2]
[2,3]
[1,2,3]
Maximum Element :
[1]
[2]
[3]
[2]
[3]
[3]
我的方法:
使用段树
查询的最大元素present在区间
code:
My Approach:
Using Segment Tree
Query The maximum element Present in a interval
Code:
public static void get_max_freq(int a , int b , ArrayList<Long> freq ,ArrayList<Integer> P , int n , int[] A){
if(a>b) return;
int index = query(1,0,n, a, b, A); // Segment Tree O(Logn)
long temp = (index-a+1)*(b-index+1);
freq.add(temp);
P.add(A[index));
get_max_freq(a,index-1, freq, P, n, A);
get_max_freq(index+1, b, freq, P,n, A);
}
我不知道是我的解决方案是正确的,如果的元素不是数组中的唯一。 有蚂蚁比这更快,更好的解决方案。
I wondering is my solution is correct if the elements are not unique in an array. Is there ant faster and better solution than this.
我觉得你过分复杂的。为了构建一个线段树,你将需要 O(nlogn)
的空间,你会在 O(N)
的时间做到这一点。在此之后,你需要回答你的 N(N + 1)/ 2
查询每个需要O(LOGN),所以基本上你将花费你为O(n ^ 2 * LOGN)
。
I think you are overcomplicating it. To construct a segment tree you will need O(nlogn)
space and you will do this in O(n)
time. After this you will need to answer your n(n+1)/2
queries each of which will take O(logn), so basically you it will cost you O(n^2*logn)
.
猜解的方法(获得所有的时间间隔,并计算他们每个人的最大)将在 O(N)
内存和 0运行(N ^ 3)
。
Bruteforce approach (get all intervals and calculate the maximum on each of them) would run in O(n)
memory and O(n^3)
.
但是你可以计算出所有与以下易于算法的最大值。让你的阵列 [A0,A1,A2,...,一]
。先从0个元素,并计算在范围内的所有的最大值开始的这个元素: MAX(A0-A0),MAX(A0-A1),...... MAX(A0级的)
。你可以做到这一点 O(N)
,仅仅因为 MAX(AI-AN)= MAX(最大(AI-A(N-1) ),一个)
(previous最大和当前元素)。所以,你计算的值,A0,A1,然后等在为O(n ^ 2)
。您可以存储它们,然后抓住其输出你想要的格式。你结束了为O(n ^ 2)
空间和时间有一个超级简单的算法。
But you can calculate all the maximums with the following easy algorithm. Let your array be [a0, a1, a2, ..., an]
. Start with 0-th element and calculate all their maximums on the range starting with this element: max(a0-a0), max(a0-a1), ... max(a0-an)
. You can do this in O(n)
, just because max(ai-an) = max( max(ai-a(n-1)), an)
(previous maximum and current element). So you calculate the values for a0, then a1 and so on in O(n^2)
. You can store them and then grab output them in the format you want. You ended up with O(n^2)
space and time with a super easy algorithm.
PS 注意,你不能这样做比更好地为O(n ^ 2)
的时候,因为你至少需要输出 N *(N + 1)/ 2
元素,所以你只能希望降低空间复杂度。
P.S. notice that you can not do better than O(n^2)
in time, because you need to at least output n*(n+1)/2
elements, so you can only hope to reduce space complexity.