1093 : หยิบหนังสือ
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 16 megabyte(s)
เนื่องจากคุณมาเข้าแถวสาย คุณจึงโดนทำโทษให้จัดหนังสือในห้องสมุด หนังสือแต่ละเล่มที่คุณจัดล้วนแต่เป็นหนังสือเรียนหนา ๆ น่าเบื่อ  ทันทีที่ถึงเวลาพักเที่ยงและอาจารย์ห้องสมุดของคุณไม่อยู่ คุณจึงคิดเกมหนึ่งขึ้นมาเล่นกับตัวเอง

เกมนี้คุณคิดเองเล่นเองคนเดียว เริ่มต้นจากมีหนังสืออยู่ n เล่มวางเรียงอยู่บนกองเดียวกันกองหนึ่ง หนังสือแต่ละเล่มถูกติดหมายเลขไว้บนสันปก ซึ่งเป็นจำนวนเต็มไม่ติดลบซึ่งมีค่าไม่เกิน 1,000,000

คุณสามารถหยิบหนังสือออกจากได้ทีละสามเล่มที่อยู่ติดกัน  แต้มที่ได้จากการหยิบหนังสือหนึ่งครั้งเกิดจากการนำหมายเลขของหนังสือสองเล่มบนรวมกันแล้วหักด้วยหมายเลขของหนังสือเล่มล่าง  คุณสามารถหยิบหนังสือออกมาได้หลาย ๆ ครั้ง เพื่อทำให้ผลรวมแต้มของการหยิบหนังสือออกมามีค่ามากที่สุดเท่าที่ทำได้  อนึ่งคุณไม่จำเป็นต้องหยิบหนังสือออกจนหมดทั้งกอง

งานของคุณ

    จงเขียนโปรแกรมรับหมายเลขของหนังสือ n เล่มในกองจากบนลงล่าง แล้วให้ตอบผลรวมแต้มที่มากที่สุดที่ทำได้จากการหยิบหนังสือนี้

ข้อมูลนำเข้า

    บรรทัดที่ 1 มีจำนวนเต็มบวก N (1≤N≤2,000) แทนจำนวนหนังสือในกอง
    บรรทัดที่ 2 ถึงบรรทัดที่ N+1 จะบอกหมายเลขหนังสือในกอง จากบนลงล่าง บรรทัดละหนึ่งจำนวน ซึ่งจำนวนเต็มไม่ติดลบดังกล่าวมีค่าไม่เกิน 1,000,000

ข้อมูลส่งออก

    มีจำนวนเต็มจำนวนเดียวแต้มรวมที่มากที่สุดที่เป็นไปได้จากการหยิบหนังสือตามเงื่อนไข

โจทย์โดย:
วรภัทร จรางกูล
ที่มา:
ดัดแปลงจากข้อสอบพี่ช่วยน้อง โรงเรียนมหิดลวิทยานุสรณ์ พ.ศ. 2552
ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
7
1
2
3
4
5
6
7
5
9
5
5
5
5
5
5
5
5
100
10
15
28
40
39
88
37
46
18
25
39
50
67
40
19
74
23
385

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 18 ผู้เยี่ยมชมและ 3 สมาชิก (1 บอท)