小 W 有一个用大写字母串成的项链，有一天，他想把项链从中间某位置剪断，拉成一条直线后形成一个线性的字母串，其价值为每个字母的字典序位置\*位置号的和。
所谓字典序位置指该字母在 26 个字母表中排在第几个位置；位置号指该字母在字符串中排在第几个位置。
现在的问题是：该从哪里截断，才能让这个线性串的价值最大？
如：WJOI 组成的项链， ，可能的截断后的线性串有：
IW 中间截断，拉直后是WJOI，价值为：23\*1+10\*2+15\*3+9\*4=124
JO 中间截断，拉直后是OIWJ，价值为：15\*1+9\*2+23\*3+10\*4=142
WJ 中间截断，拉直后是JOIW，价值为：10\*1+15\*2+9\*3+23\*4=159
OI 中间截断，拉直后是IWJO，价值为：9\*1+23\*2+10\*3+15\*4=145
其中最大的价值为：159

一个只包含大写英文字母的字符串，最大长度不超过100000。

一个整数，表示最大的价值。

【数据范围】
10%的数据，串长=1。
另外 10%的数据，串长=2。
50%的数据，串长≤1000。
100%的数据：1≤串长≤100000。

2019 年武进区第 12 届程序设计比赛试题-小学组 T5

区赛字符串前缀和差分