АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Лаурэнд дараагийн хэдэн жилийн байшингийн үнийн прогноз байгаа.

Тэрээр үл хөдлөх хөрөнгийн худалдаа эрхэлдэг ба нэг жил байшин аваад дараагийн өөр жилд буцаан зах зээлд борлуулдаг.

Гэвч одоогийн түүний прогнозоор байнга алдагдалтай ажиллахаар байгаа ба тэр санхүүгийн алдагдлаа хамгийн бага байлгахыг зорьж байгаа.

Жишээ нь

Байрны үнэ дараагийн n = 5 жилд price = [20, 15, 8, 2, 12] гэж үнэлэгдсэн.

Лаурэн дурын нэг жилд байшин худалдаж авч болох бөгөөд тэр дараагийн аль нэг жилд заавал гарзтай зарах ёстой.

Хамгийн бага гарзтай худалдаа нь 2 дахь жилд $15 үнэтэй худалдан аваад 5 дахь жилд $12 үнэтэй буцаан зарна.

Хэрэв тэр заавал дараагийн N жилд гарзтай зарах ёстой бол Лаурэн хамгийн багадаа хэдийн гарзтай байх вэ?

Тэмдэглэл

Боломжит хариу байгаа нь батлагдсан.

Функцийн тайлбар

MinimumLoss гэдэг функцийг бичнэ үү. Боломжит хамгийн бага гарзыг илтгэх бүхэл тоо хэвлэх ёстой.

MinimumLoss доорх өгөгдлийг хүлээн авна

• price: жил бүрийн үнийг илтгэсэн бүхэл тоон дараалал

Оролтын бүтэц

Эхний мөрөнд бүхэл тоо n. Жилийн тоо

Дараагийн мөрөнд n ширхэг зайгаар тусгаарлагдсан бүхэл тоонууд price[i] өгөгдөнө.

Хязгаарлалт

 2 <= n <= 2 x 10⁵

1 <= price[ i ] <= 10⁶

Үнэ бүр хоорондоо ялгаатай.

Зөв хариулт байгаа.

Дэд даалгавар

2 <= n <= 1000; онооны 50%

Гаралтын бүтэц

Хамгийн бага гарзыг илэрхийлсэн бүхэл тоог хэвлэ.

Жишээ

Оролт 1

3

5 10 3

Гаралт 1

2

Тайлбар 1

Лаурэн 1-р жилд $5-оор худалдан аваад 3 дахь жилд $3-оор зарна. 5-3=2

Оролт 2

5

20 7 8 2 5

Гаралт 2

2

Тайлбар 2

Лаурэн 2-р жилд $7-оор худалдан аваад 5 дахь жилд $5-оор зарна. 7 – 5 = 2

Орчуулсан : Б.Мөнхбаяр АНУ