內容
桌上有 N 張卡片，每張卡片上都有標註一個大於 0 的整數，參與者要不停的從中抽掉一張卡片(不再放入其中)，
而獲得的累加獎金數為此張卡片的左右兩張卡片的點數乘積。
注意第一張卡片與最後一張卡片不能抽取，抽到最後也是只剩下這兩張卡片，請問最後可獲得的獎金最大值為何？
<例如>有 5 張卡片: 5 10 7 8 4
抽卡的順序可以如下
10 -> 7 -> 8 ---> 獎金 = 35 + 40 + 20 = 95
10 -> 8 -> 7 ---> 獎金 = 35 + 28 + 20 = 83
8 -> 7 -> 10 ---> 獎金 = 28 + 40 + 20 = 88
事實上，如下的抽取順序可以獲得最多的獎金
7 -> 8 -> 10 ---> 獎金 = 80 + 40 + 20 = 140
輸入說明
多筆測資，每筆測資兩行，
第一行一個整數 N (N<=1000)，
第二行有 N 個整數 (1~100)
EOF 結束
輸出說明
每筆測資一行輸出，可以獲得的最大獎金數。
範例輸入
#1
4 3 5 10 9 5 5 10 7 8 4 5 5 10 7 8 6
範例輸出
#1
72 140 170
測資資訊：
記憶體限制：
64
MB
提示 ：
標籤: