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).
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:
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.
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?