【算法设计与分析实训】第1关：求序列的最大字段和

务描述
本关任务：编写用动态规划解决最大字段和问题。

相关知识
为了完成本关任务，你需要掌握：动态规划。

编程要求
给定由n个整数（可能为负数）组成的序列：a1,a2,……,an, 求该序列的最大子段和。当所有整数均为负数，定义其最大子段和为0。

解题思路：
定义b[j]=max(a[i]+a[i+1]+…+a[j])，其中1<=i<=j，并且1<=j<=n。那么所求的最大子段和可以表示为max b[j]，1<=j<=n。
由b[j]的定义可知，当b[j−1]>0时b[j]=b[j−1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归表达式为:
b[j]=max(b[j−1]+a[j],a[j])，1<=j<=n。

测试说明
平台会对你编写的代码进行测试：

测试输入：

6
-2 11 -4 13 -5 -2

输出示例：

20

开始你的任务吧，祝你成功！

package step1;
import java.util.Scanner;
 public class MaxSubSum{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取第一个整数N，表示数组的长度
        int n = scanner.nextInt();
        // 创建两个整型数组，a用于存储输入的整数，b用于动态规划存储的中间结果，
        int[] a = new int[n + 1];
        int[] b = new int[n + 1];
        // 初始数组第0个元素为0
        a[0] = 0;
        b[0] = 0;

        // 读取n个整数，存入数组a中

        for (int i = 1; i < n + 1; i++) {//小于10
            a[i] = scanner.nextInt();
        }
        // 关闭scanner对象

        scanner.close();

        // 初始化最大子数组和为0
        int maxnum = 0;

        // 动态规划计算最大子数组的和
        for (int i = 1; i <= n; i++) {//这个地方的等于9
            b[i] = max(b[i - 1] + a[i], a[i]);
            // 更新全局最大子数组的和

            maxnum = max(maxnum,b[i]);
        }

        // 输出最大子数组的和
        System.out.println(maxnum);
    }

    // 辅助
    private static int max(int x, int y) {
        if (x >= y) {
            return x;
        }
        return y;
    }
}

具体解释

这段代码是用来解决“最大子数组和”问题的，常见的动态规划问题。题目要求找到一个连续子数组，使得这个子数组的元素之和最大。你给出的代码实现了这个算法，并使用了动态规划的思想来解决。

代码步骤解释

1. 输入处理：

   • 代码首先从输入中读取一个整数 n，表示数组的长度。
   • 然后，创建了两个数组 a 和 b，它们的大小都为 n + 1，并初始化了这两个数组的第一个元素 a[0] 和 b[0] 为 0。
   • 数组 a 用于存储输入的整数（即题目给定的数组）。
   • 数组 b 用来存储动态规划计算的中间结果，表示以某个元素结尾的最大子数组和。

2. 填充输入数据：

   • 程序通过 for 循环读取接下来的 n 个整数，填充到数组 a 中。

3. 动态规划计算：

   • 程序使用动态规划来计算最大子数组和。b[i] 表示以 a[i] 这个元素结尾的子数组的最大和。
   • 对于每个 i，b[i] 是由以下两者中的较大值决定的：
     • b[i - 1] + a[i]：表示将当前元素 a[i] 加入到前面子数组的和中，形成一个新的子数组。
     • a[i]：表示以当前元素 a[i] 开始一个新的子数组。
   • 动态规划的核心思想就是选择这两个中的最大值，确保我们在每一步都得到最大的子数组和。

4. 更新最大值：

   • 每次计算出 b[i] 后，程序更新一个变量 maxnum，记录迄今为止的最大子数组和。

5. 输出结果：

   • 最终，程序输出 maxnum，即最大子数组的和。

辅助方法 max(int x, int y)：

这个方法简单地返回 x 和 y 中较大的那个值，用于在动态规划过程中选择更新 b[i] 和 maxnum 时用到。

代码运行实例：

假设我们输入如下数据：

n = 5
数组 =  -2 1 -3 4 -1 2 1 -5 4

步骤解析：

1. 输入数组：a = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

   在这里，我们将 a[0] 设为 0，所以实际存储的数组 a 为：

   a = [0, -2, 1, -3, 4, -1, 2, 1, -5, 4]
   

2. 初始化 b 数组：b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

3. 计算 b 数组并更新 maxnum：

   • i = 1：
     b[1] = max(b[0] + a[1], a[1]) = max(0 + (-2), -2) = -2
maxnum = max(maxnum, b[1]) = max(0, -2) = 0

   • i = 2：
     b[2] = max(b[1] + a[2], a[2]) = max(-2 + 1, 1) = 1
maxnum = max(maxnum, b[2]) = max(0, 1) = 1

   • i = 3：
     b[3] = max(b[2] + a[3], a[3]) = max(1 + (-3), -3) = -2
maxnum = max(maxnum, b[3]) = max(1, -2) = 1

   • i = 4：
     b[4] = max(b[3] + a[4], a[4]) = max(-2 + 4, 4) = 4
maxnum = max(maxnum, b[4]) = max(1, 4) = 4

   • i = 5：
     b[5] = max(b[4] + a[5], a[5]) = max(4 + (-1), -1) = 3
maxnum = max(maxnum, b[5]) = max(4, 3) = 4

   • i = 6：
     b[6] = max(b[5] + a[6], a[6]) = max(3 + 2, 2) = 5
maxnum = max(maxnum, b[6]) = max(4, 5) = 5

   • i = 7：
     b[7] = max(b[6] + a[7], a[7]) = max(5 + 1, 1) = 6
maxnum = max(maxnum, b[7]) = max(5, 6) = 6

   • i = 8：
     b[8] = max(b[7] + a[8], a[8]) = max(6 + (-5), -5) = 1
maxnum = max(maxnum, b[8]) = max(6, 1) = 6

   • i = 9：
     b[9] = max(b[8] + a[9], a[9]) = max(1 + 4, 4) = 5
maxnum = max(maxnum, b[9]) = max(6, 5) = 6

4. 输出结果：

   • 最终的最大子数组和 maxnum 是 6，所以程序会输出 6。

总结：

这个算法通过动态规划方法，通过迭代每个元素来更新当前的最大子数组和。时间复杂度是 O(n)，其中 n 是数组的长度，因为我们只需要遍历一遍数组来计算最大子数组和。

深度解析举例

这段代码实现了一个经典的算法——最大子数组和问题（Maximum Subarray Problem）。具体来说，给定一个整数数组，找出其中连续子数组的最大和。这个问题可以通过动态规划来解决。

代码解释

1. 导入Scanner类：

   import java.util.Scanner;
   

   这行代码引入了Java标准库中的Scanner类，用于从控制台读取用户输入。

2. 定义主类MaxSubSum：

   public class MaxSubSum {
       public static void main(String[] args) {
           Scanner scanner = new Scanner(System.in);
   

   定义了一个名为MaxSubSum的公共类，并在其内部定义了main方法作为程序入口点。同时创建了一个Scanner对象用于读取用户输入。

3. 读取数组长度及初始化数组：

           int n = scanner.nextInt();
           int[] a = new int[n + 1];
           int[] b = new int[n + 1];
           a[0] = 0;
           b[0] = 0;
   

   用户首先输入一个整数n，表示接下来要输入的整数数量。然后创建两个大小为n+1的整型数组a和b。数组a用于存储用户输入的整数，而数组b则用于存储动态规划过程中计算得到的中间结果。这里将这两个数组的第一个元素初始化为0。

4. 读取用户输入的整数并存入数组a中：

           for (int i = 1; i <= n; i++) {
               a[i] = scanner.nextInt();
           }
           scanner.close();
   

   使用for循环依次读取n个整数，并将其存入数组a中。最后关闭scanner对象以释放资源。

5. 动态规划计算最大子数组和：

           int maxnum = 0;
           for (int i = 1; i <= n; i++) {
               b[i] = Math.max(b[i - 1] + a[i], a[i]);
               maxnum = Math.max(maxnum, b[i]);
           }
   

   初始化变量maxnum为0，用于记录当前找到的最大子数组和。通过遍历数组a，利用动态规划的思想更新数组b，使得b[i]表示以第i个元素结尾的最大子数组和。每次更新完b[i]后，检查是否需要更新全局最大值maxnum。

6. 输出结果：

           System.out.println(maxnum);
       }
   
       private static int max(int x, int y) {
           if (x >= y) {
               return x;
           }
           return y;
       }
   }
   

   最后，程序输出全局最大子数组和maxnum。此外还定义了一个辅助函数max，用于比较两个整数并返回较大者。不过实际上，在上述代码中已经使用了Math.max()函数替代了这个自定义的max函数，因此该函数并未被调用。

实例

假设用户输入如下数据：

5
-2 1 -3 4 -1 2 1 -5 4

程序执行过程如下：

1. n=5，即接下来会输入5个整数。
2. 输入的整数分别为：-2, 1, -3, 4, -1。
3. 动态规划计算最大子数组和的过程如下表所示：

最终，程序输出的结果是5，这对应于原数组中的子数组[4, -1, 2, 1]的最大和。