Consecutive elements can construct a triangle if they can be divided into 3 sets as 3 edges (sum of elements in a set is the weight of 1 edge). (n <= 10^5, 0 <= a[i] <= 10^9, each element is distinct).

For example:

n = 6, k = 3

a = [1, 3, 4, 2, 5, 9]

There are 2 ways:

1) 1, 3, 4

2) 3, 4, 2

I have tried with this:

With every segment (i, i + k – 1), I divide it into 3 subsets and calculate the sum each set.

Let a, b, c be the sum of elements of each set respectively. I check:

a+b>c

a+c>b

b+c>a

With this algorithm, it takes O(n*(3^k)) time.

I read by this by this algorithm take O(n) time but I dont’t understand why it works:

With every segment (i, i + k – 1), assume that we sorted them so we have: ai < a(i+1) < … < an.

Let:

x = ai + a(i + 2) + … + a(n – 2)

y = a(i+1) + a(i + 3) + … + a(n-1)

z = an

We have y + z > x and x + z > y (can be easily proved),

we just need to check if:

x + y > z

<=> x + y + z > 2z

So we don’t need to sort the segment, just check if sum of all elements in the segment greater than 2 times the maximum element.

We can calculate the sum by prefix sum and maximum element by Deque in O(n).

I don’t understand that in a segment, (x, y, z) could be another way to divide into 3 sets, so why is this solution true?