Hello!↵
↵
Today I have a problem. After a while, the problem turned into finding 3 elements with indice $i, j, k$ in an array $A$ of size $n$ that:↵
↵
- $1 ≤ i < j < k ≤ n$↵
- $2 * j = i + k$↵
- $n ≤ 2*10^5$↵
- $A_i ≤ 10^9$↵
↵
and $A_i + A_j + A_k$ is maximum possible!↵
↵
I wonder if the problem can be solved in a way better than the naive $O(n ^ 2)$ solution. Thank guys!
↵
Today I have a problem. After a while, the problem turned into finding 3 elements with indice $i, j, k$ in an array $A$ of size $n$ that:↵
↵
- $1 ≤ i < j < k ≤ n$↵
- $2 * j = i + k$↵
- $n ≤ 2*10^5$↵
- $A_i ≤ 10^9$↵
↵
and $A_i + A_j + A_k$ is maximum possible!↵
↵
I wonder if the problem can be solved in a way better than the naive $O(n ^ 2)$ solution. Thank guys!