0402-1练习-分治策略-算法导论第三版

本文主要是介绍0402-1练习-分治策略-算法导论第三版，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

4.1-1 所有数组元素为负

解答：所有元素为负数时，FIND—MAXiMUM-SUBARRAY 返回只有一个最小元素的数组和该元素对应的索引。

4.1-4 允许结果为空子数组

假定修改最大子数组问题的定义，允许结果为空子数组，其和为0。你应该如何修改现有的算法，使他们能运行空子数组为最终结果。

解答：判断如果原算法结果为负数，返回空数组。

4.1-5 最大子数组的线性时间算法

使用如下的思想为最子数组问题设计一个非递归的、线性时间的算法。从数组的左边界开始，由左至右处理，记录到目前为止已经处理过的最大子数组。若已知 $A[1\cdots j]$ 的最大子数组，基于如下性质将解扩展为 $A[1\cdots j+1]$ 的最大子数组： $A[1\cdots j+1]$ 的最大子数组要么是 $A[1\cdots j]$ 的最大子数组，要么是某个子数组 $A[i\cdots j+1](1\le i\le j+1)$ 。在已知 $A[1\cdots j]$ 的最大组数组的情况下，可以在线性时间内找出形如 $A[i\cdots j+1]$ 的最大子数组。

package com.gaogzhen.introductiontoalgorithms3.divideconquer;import java.util.HashMap;
import java.util.Map;/*** @author gaogzhen* @date 2024/5/23 21:05*/
public class MaxSubarrayIterative {public static Map<String, Integer> maxSubarrayIterative(int[] arr) {int n = arr.length;int maxSum = Integer.MIN_VALUE;int sum = Integer.MIN_VALUE;int low =0;int high = 0;int currentLow = 0;int currentHigh = 0;for (int i = 0; i < n; i++) {currentHigh = i;if (sum > 0) {sum += arr[i];} else {currentLow = i;sum = arr[i];}if (sum >  maxSum) {maxSum = sum;low = currentLow;high = currentHigh;}}Map<String, Integer> ret = new HashMap<>(3);ret.put("low", low);ret.put("high", high);ret.put("sum", maxSum);return ret;}public static void main(String[] args) {int[] arr = {-13, -3, -25, -20, -3, -16, -23, -18, -20, -1, -12, -5, -22, -15, -4, -7};Map<String, Integer> map = maxSubarrayIterative(arr);System.out.println(map);}
}