计数最大元素present在所有连续的子阵 [英] Counting maximum element present in all continuous subarrays

问题描述

这是数组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.

这篇关于计数最大元素present在所有连续的子阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！