最佳游览个人见解及最大子段和认识

· · 题解

讲解思路篇

首先分析题目

游客在风景线上只能从西走到东，林荫道上则可以任意行走。

也就是说，在东西（行）方向上只能由西向东走，而在南北（列）方向上可以自由选择一个风景。既然要求最大值，那在每一列上肯定都要做到最优，即求最大值。

for (int i = 1; i <= n; i++) {
     int maxn;
     scanf("%d", &maxn);
     a[i] = max(a[i], maxn);
}
每列最大值已求出，回看题目。 游客可以从旅游城的任一个十字路口开始游览，在任一个十字路口结束游览。

看到这里，题目便简化为了在一条路线中找出一段连续的和最大的子路线，即最佳游览路线————最大子段和。

附题目 最大子段和

至此，思路及关键代码已经梳理完毕，接下来就是愉快敲代码了。

注：本人第一篇题解，杜绝抄袭，核心代码前文已给出，所以不放代码了。