I don't just tell people my answers. But I'll help you to arrive at it.
First idea: assume equal intervals. Then the area under the linear pieces paired with is given by the trapezoidal rule
In looking at this formula, what values can I swap without changing the sum?
Whoops. I forgot the factor of two. It should be the following:
Here is the explanation of this formula: the LHS is merely a symbol representing, in this case, the area under all the piecewise linear functions (another way to think of it: it's the sum of all the areas of the trapezoids).
The RHS of this formula shows you how to compute that area. To get this formula, merely note that the width of each trapezoid is equal to the width of the whole interval divided by the number of intervals, which is
Now, the area of the jth trapezoid is given by (merely translating the formula you gave me):
You can think of this expression as the width times the average of the heights on the right and left sides of the subinterval. Does this make sense?
Now, if I add all those areas up, I get this:
All the middle terms are in the sum twice, and the endpoints are there only once.
Does this make the formula clear to you?
Your test case has non-uniform x-intervals, for which the formula here is invalid. If you have non-uniform x-intervals, then you have to use the more general formula:
For your test case, this more general formula yields
I don't think the correct answer is 7. Check your work again.
I think you might find it easier to work with the uniform-interval formula. It certainly provides more ideas readily to my mind.
here in the second test case
https://www.spoj.pl/problems/INTEGMAX/
Ah, I see it now. Well, the author is contradicting himself there. The picture at the beginning of that file is precisely the same test case as the one where, later, he says the area is 7. The 7 is a typo. Trust me, the answer is 6. The author was correct the first time.
i know that sokution of picture is 6
but when you change Y,s to this range
1,2,2,1
the answer will be seven
some one give me hint
he told me about trapiziums , and said that each height will be x2-x1 and so on but he left for me to choose Y,s
and his solution accepted???
Well, for the uniform interval case, with area formula given and explained in Post # 33, I think it's fairly clear that you can swap any of the interior points (points 2 through N-1), and not change the sum, right? In addition, you can swap the two endpoints (points 1 and N) without changing the sum. Does that suggest anything to you?
I don't yet have a theory for the non-uniform case, although I do have some ideas. I'll have to think about it.
The algorithm you posted in Post # 41 is a mystery to me. Where you found that algorithm, is there an explanation for why it produces the maximized area?