小 W 有一个用大写字母串成的项链，有一天，他想把项链从中间某位置剪断，拉成一条直线后形成一个线性的字母串，其价值为每个字母的字典序位置 \ast 位置号的和。

所谓字典序位置指该字母在 26 个字母表中排在第几个位置；位置号指该字母在字符串中排在第几个位置。

现在的问题是：该从哪里截断，才能让这个线性串的价值最大？

如：WJOI 组成的项链， ，可能的截断后的线性串有：

IW 中间截断，拉直后是 WJOI，价值为：23\ast1+10\ast2+15\ast3+9\ast4=124；

JO 中间截断，拉直后是 OIWJ，价值为：15\ast1+9\ast2+23\ast3+10\ast4=142；

WJ 中间截断，拉直后是 JOIW，价值为：10\ast1+15\ast2+9\ast3+23\ast4=159；

OI 中间截断，拉直后是 IWJO，价值为：9\ast1+23\ast2+10\ast3+15\ast4=145；

其中最大的价值为：159。

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

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

【数据范围】

10\% 的数据，串长 =1。

另外 10\% 的数据，串长 =2。

50\% 的数据，串长 ≤1000。

100\% 的数据：1≤ 串长 ≤100000。

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

区赛字符串前缀和差分