使用分治算法寻找数组最大值与最小值

"该代码示例展示了如何使用分治算法在数组中找到最大值和最小值。" 在计算机科学中，分治算法是一种解决问题的有效策略，它将一个复杂的问题分解成若干个规模较小的相同问题，然后递归地解决这些子问题。这个过程一直持续到子问题变得足够简单，可以直接求解。在处理大型数据集时，分治方法往往能够提高效率和可读性。 在给定的代码中，我们有一个名为`div`的函数，用于实现分治策略。该函数接受两个参数，`lo`和`hi`，代表数组`s`的一个子区间。函数首先检查`hi`是否等于`lo+1`，这是一个基本情况，意味着子区间只包含一个元素。在这种情况下，函数会比较并交换`lo`和`hi`位置的元素（如果必要），然后更新全局的最大值`max`和最小值`min`。 如果子区间包含多个元素，函数会计算中间位置`mid`，然后递归调用自身处理左半部分`div(lo, mid)`和右半部分`div(mid + 1, hi)`。这样，每个子区间都会继续被划分，直到最后只剩下一个元素。 在`main`函数中，程序读取用户输入的测试用例数量`T`和每组测试用例的数组长度`n`。然后，它会初始化`max`为一个非常大的负数，`min`为一个非常大的正数，以确保任何可能的元素值都能覆盖。接下来，读取数组`s`的元素，并调用`div`函数找到最小值和最大值。最后，程序打印出每组测试用例的结果。 对于给定的输入，例如： ``` 4 1234 8 12345678 0 ``` 程序会输出： ``` Case1: Min:1 Max:4 Case2: Min:1 Max:8 ``` 这表明，对于每个输入数组，程序正确地找到了最小值和最大值。在第一个案例中，数组`1234`的最小值是1，最大值是4；在第二个案例中，数组`12345678`的最小值是1，最大值是8。 这段代码演示了如何利用分治算法在数组中寻找最大值和最小值，同时展示了递归和分治策略的基本应用。虽然在实际应用中，更常见的是使用线性扫描法来寻找这些值，但这个例子有助于理解分治算法的概念。