hoang25's blog

By hoang25, history, 3 weeks ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Your problen description doesn't look correct.

Given your current description, there is no constraint between the array values. So we can simply choose any i, j and k that fulfill $$$2*j=i+k$$$ and $$$1\le i < j < k \le n$$$. The array elements are kind of irrelevant here.

»
3 weeks ago, # |
Rev. 8   Vote: I like it +5 Vote: I do not like it

[Deleted]

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hoang25 (previous revision, new revision, compare).