主页 / 问题 / 961901
Accepted
Kekw1x
Asked:2020-03-27 15:13:50 +0800 CST2020-03-27 15:13:50 +0800 CST

确定小于 O(n^2) 的函数的最大值

  • 772

我不知道如何正确优化 O(n^2) 算法：

 public static long kodyara(long[] arr,long max)
 {
   for (int i = 0; i < arr.length; i++)

         for (int j = 0; j < arr.length; j++) 
         {
             long val = arr[i] * (j+1) + arr[j] * (1 + i);
             max = Math.max(val, max);
         }
     }
  return max;
 }

提出建议

问题状况( https://algotester.com/en/ArchiveProblem/Display/40366 )

给出：

  • 维度为 N 的整数数组 A (1 < N < 100000, 1 < A[i] < 1000)
  • 功能f(i,j) = A[i] * j + A[j] * i

我们需要找到函数的最大值。

例子：

5-N

100 1 1 1 1

最大501

另一个例子：

1-N

一

最大2

java

2 个回答

  1. Best Answer

    对数组元素值的限制 (1 < A[i] < 1000) 大大简化了任务：

    健康）状况

    正如@pavel 已经写的那样，只有当序列中没有更大的数字时，一个数字才能成为最大对。

    这很容易证明：如果i并且 和j为真i<j，a[i]<=a[j]那么对于任何值x， 都为真a[x]*i + x*a[i] < a[x]*j + x*a[j]。

    因此，如果一个数字不是其后缀中的最大值（从数字到数组末尾的子数组），它可能不会被认为是选择的候选者。

    选择

    因此，提出了一种方法：从末尾遍历数组，更新最大值并记住更新最大值的元素。函数的最大值总是在一对这样的元素上达到。

    例子：

    Для массива:
позиция:  1   2 3 4 5
значение: 100 1 1 1 1
будут отобраны элементы
позиция:  1         5
значение: 100       1
Остальные не имеет смысла рассматривать, т.к. справа от них в массиве встречается равное им значение.

Для массива:
позиция:  1 2 3 4 5
значение: 5 1 4 1 2
будут отобраны элементы
позиция:  1   3   5
значение: 5   4   2

    我们得到数组后缀中最大元素的严格递减子序列。因为 数组元素可以取1000个值中的一个，并且没有一个等于另一个，那么数组的长度不会超过1000。

    选择后，我们有一个index长度为 L (L < 1000) 的数组，其中index[i]是元素在原始数组中的位置（选择前）。按位置，通过a你可以获得值

    计算

    现在您只需要解决生成的子数组的问题，即找到这样的一对iand j，对于 which index[i]*value[j] + index[j]*value[i]。

    这已经可以通过检查所有可能的元素对通过双循环来完成。这将需要 L^2/2 次操作。

    相同的例子：

    1. Для массива:
       100 1 1 1 1
отобраны элементы
index: 1         5
value: 100       1
Проверяем все возможные сочетания для L = 2:
i = 0, j = 0: index[0]*value[0]+index[0]*value[0] = 1*100 + 1*100 = 200
i = 0, j = 1: index[0]*value[1]+index[1]*value[0] = 1*1   + 100*5 = 501
i = 1, j = 1: index[1]*value[1]+index[1]*value[1] = 5*1   + 5*1   = 10
Ответ: f(1, 5) = 501

2. 
a:     5 1 4 1 2
index: 1   3   5
value: 5   4   2
Все возможные пары:
i = 0, j = 0: index[0]*value[0]+index[0]*value[0] = 1*5+1*5 = 10
i = 0, j = 1: index[0]*value[1]+index[1]*value[0] = 1*4+3*5 = 19
i = 0, j = 2: index[0]*value[2]+index[2]*value[0] = 1*2+5*5 = 27
i = 1, j = 1: index[1]*value[1]+index[1]*value[1] = 3*4+3*4 = 24
i = 1, j = 2: index[1]*value[2]+index[2]*value[1] = 3*2+5*4 = 26
i = 2, j = 2: index[2]*value[2]+index[2]*value[2] = 5*2+5*2 = 20
Ответ: f(1, 5) = 27

    伪代码

    int n = a.length;

//Текущий максимум
int max = -1;
//Индексы отобранных элементов
//выделено n ячеек с «запасом» (можно 1000)
int[] index = new int[n];
//их количество
int l = 0;
//идем с конца
for (int i = n - 1; i >= 0; i--) {
    if (a[i] > max) {
        //записываем максимум
        max = a[i];
        //и индекс
        index[l++] = i;
    }
}

//рассчитываем значения функции для отобранных элементов
int result = -1;
for (int i = 0; i < l; i++) {
    for (int j = i; j < l; j++) {
        int f = (index[i] + 1) * a[index[j]] + (index[j] + 1) * a[index[i]];
        result = max(result, f);
    }
}
return result;

    复杂

    那。该算法将在 O(N + L^2) 中运行，其中 ，其中 L 是数组后缀的最大元素的子序列的长度。

    解决方案以某种方式通过只是由于对A[i]. 也许有一种使用递归关系或数据结构的通用方法。

    • 4

  2. 答案已经改变。

    让我们修复i。考虑最优 j。

    arr[i] * (j+1) + arr[j] * (1 + i) -> max.

    或者（记住，i 是一个常数）。

    (arr[i]/(i+1)) * (j+1) + arr[j] -> max

    除以 (j+1) 是不可能的（那么最大值的不变量会改变）。

    If i < i1and a[i] < a[i1]then 这个元素i对我们完全不感兴趣。因此，我们可以假设a[i] > a[i+1]。

    让我们计算S[j]最大元素。（这是我们感兴趣的第一个）。

    i从to移动时会发生什么i+1：乘数会减少 arr[i]/(i+1)（arr[i+1] - 更少，i+1 - 更多）。

    事实上 S[i+1,j] = S[i,j] - j* [乘数差]。

    我们需要支持最大值。任何带有间隔修改的树都可以用于此目的。特别是线段树（你也可以使用 Fenwick，但写在那里会更难）。

    复杂度 O(N log N)。Fenwick 树的内存为 O(N)，段树的内存为 O(N log N)。

    PS最好不要进行分数运算。

    • 2

相关问题