数据结构和算法 最大和连续子数组
2023-09-14 09:15:03 时间
一、问题描述
最大和连续子数组(maximum subarray):目的是为了在一维数字数组中找到最大的连续子数组的和。
如下图所示
这个问题可以使用几种不同的算法技术来解决,包括暴力、分而治之、动态规划、减少到最短路径等,我们这里主要关注动态规划算法。
二、算法示例
对于下面给出的数组,总和最大的连续子数组是 [4, -1, 2, 1],总和为 6。我们将使用这个数组作为本文其余部分的示例。
1、暴力算法
Java参考代码如下
public int FindSubarrayByViolence(int[] array) {
int n = array.length;
int MaxSum = array[0];
for(int i = 0 ; i < n ; i ++){
int temp = 0;
for(int j = i; j < n ; j ++ ){
temp += array[j];
MaxSum = MaxSum > temp ? MaxSum : temp;
}
}
return MaxSum;
}
如果数组的大小是n,那么这个解决方案的时间复杂度是O(n²)。
2、Kadane算法
Kadane算法使用最优子结构的方式(在每个位置结束的最大子数组是从一个相关但较小且重叠的子问题中以简单的方式计算出来的:在前一个位置结束的最大子数组)这个算法可以被视为一个简单的例子的动态规划。Kadane算法能够在运行时间为O(n)的数组中找到连续子数组的最大和。
伪代码描述如下
初始化:
max_so_far = INT_MIN
max_ending_here = 0
循环数组的每个元素
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
(c) if(max_ending_here < 0)
max_ending_here = 0
返回 max_so_far
Kadane 算法的简单思想是寻找数组的所有正连续段(max_ending_here 用于此)。并跟踪所有正段之间的最大和连续段(max_so_far 用于此)。每次我们得到一个正和时,将其与 max_so_far 进行比较,如果它大于 max_so_far 则更新 max_so_far 。
(1)Java参考代码1
import java.io.*;
import java.util.*;
class Kadane
{
public static void main (String[] args)
{
int [] a = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println("Maximum contiguous sum is " +
maxSubArraySum(a));
}
static int maxSubArraySum(int a[])
{
int size = a.length;
int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;
for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
}
return max_so_far;
}
}
(2)Java参考代码2
import java.io.*;
class GFG {
static int maxSubArraySum(int a[], int size)
{
int max_so_far = a[0];
int curr_max = a[0];
for (int i = 1; i < size; i++)
{
curr_max = Math.max(a[i], curr_max+a[i]);
max_so_far = Math.max(max_so_far, curr_max);
}
return max_so_far;
}
public static void main(String[] args)
{
int a[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = a.length;
int max_sum = maxSubArraySum(a, n);
System.out.println("Maximum contiguous sum is " + max_sum);
}
}
(3)Java参考代码3,获取起止索引
class Temp {
static void maxSubArraySum(int a[], int size)
{
int max_so_far = Integer.MIN_VALUE,
max_ending_here = 0,start = 0,
end = 0, s = 0;
for (int i = 0; i < size; i++)
{
max_ending_here += a[i];
if (max_so_far < max_ending_here)
{
max_so_far = max_ending_here;
start = s;
end = i;
}
if (max_ending_here < 0)
{
max_ending_here = 0;
s = i + 1;
}
}
System.out.println("Maximum contiguous sum is " + max_so_far);
System.out.println("Starting index " + start);
System.out.println("Ending index " + end);
}
public static void main(String[] args)
{
int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
int n = a.length;
maxSubArraySum(a, n);
}
}
相关文章
- 构建算法模型_模型与算法有什么不同
- 检测模型改进—OHEM与Focal-Loss算法总结[通俗易懂]
- Python ---- 算法入门(2)分治算法解决【找数组的最大值和最小值】问题
- 算法死活记不住?大神告诉你秘诀:内化它的逻辑
- Python遗传和进化算法框架(一)Geatpy快速入门[通俗易懂]
- Java数组常用算法
- 日拱算法:两个数组的交集(I、II)
- 【沥血整理】灰度(二值)图像重构算法及其应用(morphological reconstruction)。
- 【JavaScript——牛客网算法No.HJ2】计算一个字符串中含有某个字符的个数[通俗易懂]
- 为什么Adam 不是默认的优化算法?
- hanoi塔问题如下图所示_hanoi塔问题最经典的算法
- 前端leetcde算法面试套路之回溯_2023-02-27
- 大数据Kylin(六):Kylin构建Cube算法
- Stable Diffusion采样速度翻倍!仅需10到25步的扩散模型采样算法
- [量化]夏普比率3.27,通过DQN算法进行上证指数择时强化学习策略
- R语言高维数据的主成分pca、 t-SNE算法降维与可视化分析案例报告|附代码数据
- BAT面试算法进阶(8)- 删除排序数组中的重复项
- 干货 | AI算法透明性实现与评估
- 【算法】快速选择算法 ( 数组中找第 K 大元素 )
- 【算法】二分法 ③ ( 山脉数组的峰顶索引 | 枚举法 | 二分法 )
- Go 实现二分查找算法
- Scalaz(34)- Free :算法-Interpretation详解编程语言
- Java数据结构和算法(十)——二叉树详解编程语言
- 算法-二维数组中的查找详解编程语言
- 对称二叉树算法详解编程语言
- 寻找两个有序数组的中位数算法详解编程语言