First idea: assume equal intervals. Then the area under the linear pieces $\{x_{1},\dots,x_{N}\}$ paired with $\{y_{1},\dots,y_{N}\}$ is given by the trapezoidal rule

$\int_{x_{1}}^{x_{N}}f(x)\,dx=\frac{x_{N}-x_{1}}{N}(y_{1}+2y_{2}+2y_{3}+\dots+2y_{N-1}+y_{N}).$

In looking at this formula, what values can I swap without changing the sum?

2. Originally Posted by Ackbeet

First idea: assume equal intervals. Then the area under the linear pieces $\{x_{1},\dots,x_{N}\}$ paired with $\{y_{1},\dots,y_{N}\}$ is given by the trapezoidal rule

$\int_{x_{1}}^{x_{N}}f(x)\,dx=\frac{x_{N}-x_{1}}{N}(y_{1}+2y_{2}+2y_{3}+\dots+2y_{N-1}+y_{N}).$

In looking at this formula, what values can I swap without changing the sum?
i can't understand anything from these formula

3. Whoops. I forgot the factor of two. It should be the following:

$\displaystyle{\int_{x_{1}}^{x_{N}}f(x)\,dx=\frac{x _{N}-x_{1}}{2N}(y_{1}+2y_{2}+2y_{3}+\dots+2y_{N-1}+y_{N})}.$

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

$\displaystyle{\frac{x_{N}-x_{1}}{N}}.$

Now, the area of the jth trapezoid is given by (merely translating the formula you gave me):

$\displaystyle{\frac{x_{N}-x_{1}}{N}\left(\frac{y_{j}+y_{j+1}}{2}\right)}.$

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:

$\displaystyle{\frac{x_{N}-x_{1}}{N}\left(\frac{y_{0}+y_{1}}{2}+\frac{y_{1}+y _{2}}{2}+\dots+\frac{y_{N-1}+y_{N}}{2}\right)}$

$\displaystyle{=\frac{x_{N}-x_{1}}{2N}(y_{0}+y_{1}+y_{1}+y_{2}+\dots+y_{N-1}+y_{N})}$

$\displaystyle{=\frac{x_{N}-x_{1}}{2N}(y_{0}+2y_{1}+2y_{2}+\dots+2y_{N-1}+y_{N}).}$

All the middle terms are in the sum twice, and the endpoints are there only once.

Does this make the formula clear to you?

4. Originally Posted by Ackbeet
Whoops. I forgot the factor of two. It should be the following:

$\displaystyle{\int_{x_{1}}^{x_{N}}f(x)\,dx=\frac{x _{N}-x_{1}}{2N}(y_{1}+2y_{2}+2y_{3}+\dots+2y_{N-1}+y_{N})}.$

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

$\displaystyle{\frac{x_{N}-x_{1}}{N}}.$

Now, the area of the jth trapezoid is given by (merely translating the formula you gave me):

$\displaystyle{\frac{x_{N}-x_{1}}{N}\left(\frac{y_{j}+y_{j+1}}{2}\right)}.$

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:

$\displaystyle{\frac{x_{N}-x_{1}}{N}\left(\frac{y_{0}+y_{1}}{2}+\frac{y_{1}+y _{2}}{2}+\dots+\frac{y_{N-1}+y_{N}}{2}\right)}$

$\displaystyle{=\frac{x_{N}-x_{1}}{2N}(y_{0}+y_{1}+y_{1}+y_{2}+\dots+y_{N-1}+y_{N})}$

$\displaystyle{=\frac{x_{N}-x_{1}}{2N}(y_{0}+2y_{1}+2y_{2}+\dots+2y_{N-1}+y_{N}).}$

All the middle terms are in the sum twice, and the endpoints are there only once.

Does this make the formula clear to you?
but with this formula and the test case :
4
2 3 5 6
1 2 1 2

= (6-2)/(2*4)*(1+4+2+2)=4.5
and the correct answer is 7

5. 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:

$\displaystyle{\int_{a}^{b}f(x)\,dx=\frac{1}{2}\sum _{j=2}^{N}(x_{j}-x_{j-1})(y_{j}+y_{j-1}).}$

For your test case, this more general formula yields
$\displaystyle{\int_{a}^{b}f(x)\,dx=\frac{1}{2}\lef t[1\times 3+2\times 3+1\times 3\right]=\frac{1}{2}\,(4\times 3)=6.}$

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.

6. Originally Posted by Ackbeet
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:

$\displaystyle{\int_{a}^{b}f(x)\,dx=\frac{1}{2}\sum _{j=2}^{N}(x_{j}-x_{j-1})(y_{j}+y_{j-1}).}$

For your test case, this more general formula yields
$\displaystyle{\int_{a}^{b}f(x)\,dx=\frac{1}{2}\lef t[1\times 3+2\times 3+1\times 3\right]=\frac{1}{2}\,(4\times 3)=6.}$

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.
thx i will try now but the correct answer is really 7 see problem link thx ackbeet >>

7. Where do you get 7? I quote from the link:

...the integral of the polygonal line is the shaded area, with a value of 6.

8. Originally Posted by Ackbeet
Where do you get 7? I quote from the link:
here in the second test case
https://www.spoj.pl/problems/INTEGMAX/

9. 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.

10. Originally Posted by Ackbeet
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
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???

11. i found a solution
i should sort Y values
then i should take height as follows
h[0]=x[1]-x[0] , h[n]=h[n]-h[n-1]
then loop from i=0 to n
h[i+1]=x[i+2]-x[i]
finally
loop from i=0 to n
sum=sum+(h[i]*y[i])

thx very much for ur help

12. Yeah, I mis-spoke. The 7 comes from the maximized area, with the assignment of y's that you mentioned in post # 40. I will have to think about your solution. Do you understand your solution as posted in Post # 41?

13. Originally Posted by Ackbeet
Yeah, I mis-spoke. The 7 comes from the maximized area, with the assignment of y's that you mentioned in post # 40. I will have to think about your solution. Do you understand your solution as posted in Post # 41?
i think that but i am waiting for ur reply about ur opinion for this solution

14. 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?

15. Originally Posted by Ackbeet
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?
my father told me that but he is in his work nw
and the solution he told me is accepted
but u make him reach this formula by your idea with trapeziums
i think u can get better formula waiting u

Page 3 of 4 First 1234 Last