1005 : Max Sequence
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
กำหนดให้ a1 , a2 , … , an เป็น ลำดับ ของจำนวนเต็ม และ กำหนดให้ ai , ai+1 , … , aj เป็น ลำดับย่อย ของลำดับดังกล่าวนี้ โดยที่ i และ j เป็นจำนวนเต็มบวก และ 1 ≤ i ≤ j ≤ n หรือกล่าวอีกนัยหนึ่งคือสมาชิกทุกตัวของ ลำดับย่อย ต้องมีตำแหน่งต่อเนื่องกัน ลำดับย่อย อาจมีได้หลายชุด เมื่อหาค่าผลบวกของสมาชิกทุกตัวใน ลำดับย่อย แต่ละชุด ผลบวกที่ได้อาจมีค่าแตกต่างกัน
ลำดับย่อย ที่มีผลบวกของสมาชิกสูงสุด เรียกว่า ลำดับย่อยที่มีค่าสูงสุด ซึ่งอาจมีเพียงชุดเดียวหรืออาจมีหลายชุดก็ได้
ในกรณีที่ ลำดับย่อยที่มีค่าสูงสุด มีค่าน้อยกว่าหรือเท่ากับศูนย์ เรียกว่า ลำดับย่อยว่าง (Empty sequence)
ตัวอย่าง
ลำดับ 4, -6, 3, -2, 6, -4, -6, 6 มี ลำดับย่อยที่มีค่าสูงที่สุด เพียงชุดเดียว คือ ลำดับย่อย 3, -2, 6 โดยผลบวกของ ลำดับย่อย มีค่าเท่ากับ 7
ลำดับ -2, -3, -1 ไม่มี ลำดับย่อย ใดที่มีผลบวกมากกว่าศูนย์ ถือว่ามี ลำดับย่อยว่าง
จงเขียนโปรแกรมเพื่อรับจำนวนของสมาชิกในลำดับ และรับค่าสมาชิกทุกตัวของลำดับนั้น ทำการคำนวณและแสดงผล ลำดับย่อยที่มีค่าสูงสุด และผลบวกของ ลำดับย่อย นั้น
ข้อมูลนำเข้า
1. ข้อมูลบรรทัดแรกเป็นจำนวนเต็มบวกซึ่งเป็นจำนวนของสมาชิกในลำดับ ค่านี้มีค่าตั้งแต่ 1 ถึง 2,500
2. ข้อมูลในบรรทัดที่สองเป็นค่าของสมาชิกของ ลำดับย่อย แต่ละลำดับ ค่าของสมาชิกแต่ละตัว คั่นแต่ละตัวด้วยเครื่องหมายเว้นวรรคจำนวน 1 วรรค ค่านี้มีค่าตั้งแต่ -127 ถึง +127
การแสดงผลลัพธ์
1. ในกรณีที่หา ลำดับย่อยที่มีค่าสูงสุด ได้เพียงชุดเดียวให้แสดง ลำดับย่อย นั้น
2. ในกรณีที่หา ลำดับย่อยที่มีค่าสูงสุด ได้หลายชุด ให้แสดงเฉพาะชุดแรกที่พบเมื่อนับจาก ต้นลำดับ เช่น ลำดับ 4, -6, 3, -2, 6, -4, -6, 6, -6, 4, -2, 5 มีลำดับย่อยที่มีค่าสูงสุด 2 ชุด คือ 3, -2, 6 และ 4, -2, 5 ซึ่งมีค่าผลบวกของ ลำดับย่อย เป็น 7 เท่ากัน ในกรณีนี้ให้แสดงคำตอบเพียงคำตอบเดียวคือ ลำดับย่อย ชุดแรกที่พบคือ 3, -2, 6
3. การแสดง ลำดับย่อยที่มีค่าสูงสุด ให้แสดงสมาชิกของ ลำดับย่อย ทั้งหมดในบรรทัดเดียวกัน โดยใช้เครื่องหมายเว้นวรรคคั่นระหว่างสมาชิกแต่ละตัวจำนวน 1 วรรค
4. บรรทัดที่สองให้แสดงผลเป็นผลบวกของ ลำดับย่อยที่มีค่าสูงสุด นั้น
5. ในกรณีที่ ลำดับย่อยที่มีค่าสูงสุด เป็น ลำดับย่อยว่าง ให้แสดงข้อความ Empty sequence โดยไม่ต้องแสดง ลำดับย่อย และผลบวกของ ลำดับย่อย นั้น
ที่มา: การแข่งขันคอมพิวเตอร์โอลิมปิก สอวน. ครั้งที่ 2 มหาวิทยาลัยบูรพา
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
ลำดับย่อย ที่มีผลบวกของสมาชิกสูงสุด เรียกว่า ลำดับย่อยที่มีค่าสูงสุด ซึ่งอาจมีเพียงชุดเดียวหรืออาจมีหลายชุดก็ได้
ในกรณีที่ ลำดับย่อยที่มีค่าสูงสุด มีค่าน้อยกว่าหรือเท่ากับศูนย์ เรียกว่า ลำดับย่อยว่าง (Empty sequence)
ตัวอย่าง
ลำดับ 4, -6, 3, -2, 6, -4, -6, 6 มี ลำดับย่อยที่มีค่าสูงที่สุด เพียงชุดเดียว คือ ลำดับย่อย 3, -2, 6 โดยผลบวกของ ลำดับย่อย มีค่าเท่ากับ 7
ลำดับ -2, -3, -1 ไม่มี ลำดับย่อย ใดที่มีผลบวกมากกว่าศูนย์ ถือว่ามี ลำดับย่อยว่าง
จงเขียนโปรแกรมเพื่อรับจำนวนของสมาชิกในลำดับ และรับค่าสมาชิกทุกตัวของลำดับนั้น ทำการคำนวณและแสดงผล ลำดับย่อยที่มีค่าสูงสุด และผลบวกของ ลำดับย่อย นั้น
ข้อมูลนำเข้า
1. ข้อมูลบรรทัดแรกเป็นจำนวนเต็มบวกซึ่งเป็นจำนวนของสมาชิกในลำดับ ค่านี้มีค่าตั้งแต่ 1 ถึง 2,500
2. ข้อมูลในบรรทัดที่สองเป็นค่าของสมาชิกของ ลำดับย่อย แต่ละลำดับ ค่าของสมาชิกแต่ละตัว คั่นแต่ละตัวด้วยเครื่องหมายเว้นวรรคจำนวน 1 วรรค ค่านี้มีค่าตั้งแต่ -127 ถึง +127
การแสดงผลลัพธ์
1. ในกรณีที่หา ลำดับย่อยที่มีค่าสูงสุด ได้เพียงชุดเดียวให้แสดง ลำดับย่อย นั้น
2. ในกรณีที่หา ลำดับย่อยที่มีค่าสูงสุด ได้หลายชุด ให้แสดงเฉพาะชุดแรกที่พบเมื่อนับจาก ต้นลำดับ เช่น ลำดับ 4, -6, 3, -2, 6, -4, -6, 6, -6, 4, -2, 5 มีลำดับย่อยที่มีค่าสูงสุด 2 ชุด คือ 3, -2, 6 และ 4, -2, 5 ซึ่งมีค่าผลบวกของ ลำดับย่อย เป็น 7 เท่ากัน ในกรณีนี้ให้แสดงคำตอบเพียงคำตอบเดียวคือ ลำดับย่อย ชุดแรกที่พบคือ 3, -2, 6
3. การแสดง ลำดับย่อยที่มีค่าสูงสุด ให้แสดงสมาชิกของ ลำดับย่อย ทั้งหมดในบรรทัดเดียวกัน โดยใช้เครื่องหมายเว้นวรรคคั่นระหว่างสมาชิกแต่ละตัวจำนวน 1 วรรค
4. บรรทัดที่สองให้แสดงผลเป็นผลบวกของ ลำดับย่อยที่มีค่าสูงสุด นั้น
5. ในกรณีที่ ลำดับย่อยที่มีค่าสูงสุด เป็น ลำดับย่อยว่าง ให้แสดงข้อความ Empty sequence โดยไม่ต้องแสดง ลำดับย่อย และผลบวกของ ลำดับย่อย นั้น
ที่มา: การแข่งขันคอมพิวเตอร์โอลิมปิก สอวน. ครั้งที่ 2 มหาวิทยาลัยบูรพา
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 8 4 -6 3 -2 6 -4 -6 6 | 3 -2 6 7 |
| 3 -2 -3 -1 | Empty sequence |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 15 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)