田忌赛马是一个历史故事演化而成的成语，是中国历史上有名的揭示如何善用自己的长处去对付对手的短处，从而在竞技中获胜的事例。
田忌和齐威王爱好赛马，两人各有上中下等马各三匹，进行三轮比赛，每次都派不同的马上场。一开始田忌总是用上等马出战齐威王的上等马，用中等马出战齐威王的中等马，用下等马出战齐威王的下等马。总是0:3输给齐威王，因为他的每个马总是比齐威王的弱一点点。
后来孙膑给田忌出了个主意，建议田忌这样调整马的上场顺序：第一局派出的下等马，对阵齐威王的上等马。第二局派出上等马对阵齐威王的中等马。第三局派出中等马对阵齐威王的下等马。最终田忌2:1获得赛马的胜利。
现在假如你是孙膑，双方各有n匹马，进行n轮比赛。在已知齐威王所有马的上场顺序和双方所有马的实力数值后。求在田忌使用最优策略的情况下，即获得赛马的最大比分差。