标题起的又一次把自己恶心到了。。
算法实现完全来源于编程之美,最简单的DP思想的实践。
maxSubSum2方法中稍作修改,记录了下该子序列的下标。
/**
* 子数组之和的最大值:要求子数组的元素是连续的
*
* @author aaron-han
*
*/
public class MaxSubSum {
public static void main(String[] args) {
int[] arr = { 3, 5, -3, -2, 5, 8, 3, -2, 1 }; // 19
int maxSum = maxSubSum2(arr, arr.length);
System.out.println("\n" + maxSum);
}
// 尾->首
// nAll保存当前的最大子数组之和,nStart保存当前的子数组之和,初值均设为最后一个元素。
public static int maxSubSum(int[] arr, int length) {
int nAll = arr[length - 1];
int nStart = arr[length - 1];
for (int i = length - 2; i >= 0; i--) {
if (nStart < 0) { // 若为负数,则清零重新寻找。
nStart = 0;
}
nStart += arr[i];
if (nStart > nAll) { // 若当前子数组之和大于nAll,则更新nAll。
nAll = nStart;
}
}
return nAll;
}
// 在遍历求值的基础上记录了子序列的index并打印
public static int maxSubSum2(int[] arr, int length) {
int nAll = arr[length - 1];
int nStart = 0;
int endIndex = length - 1;
int startIndex = length - 1;
int tempIndex = length - 1;
for (int i = length - 1; i >= 0; i--) {
if (nStart < 0) {
nStart = 0;
tempIndex = i;
}
nStart += arr[i];
if (nStart > nAll) {
nAll = nStart;
endIndex = tempIndex;
startIndex = i;
}
}
for (int i = startIndex; i <= endIndex; i++) {
System.out.print(arr[i] + "\t");
}
return nAll;
}
}
分享到:
相关推荐
### 递归算法在求解数组最大值中的应用 #### 一、递归算法简介 递归算法是一种通过调用自身来解决问题的方法。它通常包括两个部分:基本情况(base case)与递归情况(recursive case)。对于求解数组中的最大值...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
通过分治算法来求解一个数组中的最大值和最小值,不仅可以有效地降低问题的复杂度,还能充分利用计算机的处理能力。此外,这种方法还具有很好的可扩展性和并行处理潜力,非常适合于处理大规模数据集。
分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法分割数组算法
在Java编程中,数组是最基本的数据结构之一,用于存储同类型元素的集合。在处理数组时,有时我们需要找出数组中的最大或最小值。本示例介绍了一种简单且高效的算法来寻找整数数组中的最大值。 首先,我们创建了一个...
题目: 编程实现找出一组数的最大值和次大值 要求: 用二分法的策略实现; (2)写出实验报告。 一、 需求分析: 1、输入要输入数组元素的个数,为数组... 3、利用二分法找出数组中的最大值和次大值; 4、输出结果;
在处理数组时,经常会遇到需要找到数组中的最大值和最小值的问题。这通常用于统计分析、排序算法或其他数学计算中。这个程序的目标就是实现这个功能。 首先,我们需要了解C语言数组的基本概念。数组是由相同类型...
本文将详细介绍一个原创的C语言算法实现,该算法能够有效地找到数组中的最大值及其索引,并通过理解这个过程来帮助读者掌握算法思想,从而能够灵活运用到其他类似问题上。 #### 算法描述 本算法的目标是在给定的...
3. **排序子数组**:使用冒泡排序对 `C1` 和 `C2` 进行排序,从而找到每个子数组的最大值和最小值。 4. **合并结果**:将 `C1` 和 `C2` 的四个最大值合并到数组 `Max` 中,四个最小值合并到数组 `Min` 中。 5. **...
在本主题中,我们将深入探讨如何计算Java数组的和以及找到数组中的最大值。 首先,让我们了解Java数组的基本概念。数组可以通过声明数组变量并指定类型来创建,例如: ```java int[] numbers; ``` 接着,我们需要...
总结来说,求子数组最大和的问题可以通过动态规划的Kadane算法在O(n)的时间复杂度内解决。实例代码展示了如何实现这个算法,通过比较当前元素与前一个子数组和,找出能够构成更大和的策略,并在遍历过程中保持最大子...
### 知识点一:寻找数组中的最大值与次最大值...通过以上分析,我们不仅理解了如何寻找数组中的最大值和次最大值的基本算法,还深入了解了其时间复杂度分析以及可能的优化方向。这对于解决实际问题具有重要的指导意义。
总之,理解如何在Java中查找数组中的最大值和最小值是编程基础的一部分,也是解决更复杂问题的基础技能。通过这个例子,你可以学习到基本的循环和条件控制结构,以及如何应用它们来解决实际问题。
### 判断数组最大值 找出数组中的最大值,我们可以遍历数组并用一个变量记录当前找到的最大值。初始时,这个变量可以设置为数组的第一个元素,然后依次与后续元素比较。以下是实现这个功能的C#代码: ```csharp ...
总的来说,数组中的近似值查找是一个涉及到基础数据结构、搜索算法和问题解决策略的综合问题。熟练掌握这些知识,对于从事IT行业的人来说至关重要,尤其是在数据处理、算法设计和软件开发等领域。通过对给定的代码...
分治算法实验(用分治法查找数组元素的最大值和最小值) 在这个实验中,我们使用分治算法来查找数组元素的最大值和最小值。分治算法是一种常用的算法设计方法,它将问题分解成小规模的问题,然后解决这些小问题,并...
如果要获取最大值和最小值的索引,我们可以使用`max`和`min`函数的第三个输出参数,它是一个包含行和列索引的一维数组。例如: ```matlab [maxValue, ~, maxIndex] = max(matrix); [minValue, ~, minIndex] = min...
标题中的“求数组的子数组之和的最大值”是一个经典的计算机科学问题,通常被称为“最大子序列和”(Maximum Subarray Problem)。这个问题在数组或序列数据结构中寻找一段连续的子序列,使得子序列的所有元素之和...
本文介绍了一种基于Java多线程的代码迷惑算法,该算法可以隐藏数组下标变换表达式,以防止源代码静态分析和基于源代码植入反迷惑攻击。该算法的核心思想是对数组下标变换表达式进行预处理,使得表达式能够并行处理,...
通过共享内存优化,高效地查找一个序列中的最大值并将该最大值放到序列的第一个元素位置。同时,不同于传统的利用线程和数组序号对应的方式,本算法利用连续的线程进行计算,更有利于算法的并发性