20/11/29 22:05:05.40 M8xgBTYt.net
5, -7, 3, 5, -2, 4, -1
インデックスが5で終わるsliceまたは空のsliceのうち,その和が最大であるsliceは,3, 5, -2, 4です.
インデックスが6で終わるsliceまたは空のsliceのうち,その和が最大であるsliceをSとする.
Sは何になるか?
3 + 5 - 2 + 4 - 1 = 9 > 0なので,Sは空のsliceではありません.
Sは,例えば,5, -2, 4, -1ではありません.もし,Sが,5, -2, 4, -1であるとすると,
5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1
したがって,
5 - 2 + 4 > 3 + 5 - 2 + 4
となってしまい,インデックスが5で終わるsliceまたは空のsliceのうち,その和が最大であるsliceが,3, 5, -2, 4ではなく,
5, -2, 4であるということになってしまうからです.
Sは,例えば,-7, 3, 5, -2, 4, -1ではありません.もし,Sが,-7, 3, 5, -2, 4, -1であるとすると,
-7 + 3 + 5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1
したがって,
-7 + 3 + 5 - 2 + 4 > 3 + 5 - 2 + 4
となってしまい,インデックスが5で終わるsliceまたは空のsliceのうち,その和が最大であるsliceが,3, 5, -2, 4ではなく,
-7, 3, 5, -2, 4, -1であるということになってしまうからです.