编程之美之2.14 求数组的子数组之和的最大值

2024-02-19 03:18
文章标签 数组 编程 最大值 之美 2.14

本文主要是介绍编程之美之2.14 求数组的子数组之和的最大值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

一个有N个整数元素的一维数组(A[0],A[1],A[2],...A[n-1]),这个数组中当然有很多子数组，那么子数组之和的最大值是多少？

该子数组是连续的。

我们先来明确一下题意：

（1）子数组意味着是连续的。

（2）题目只需要求和，并不需要返回子数组的具体位置。

（3）数组的元素是整数，所以数组可能包含正整数，负整数或者零。

举几个例子：

数组：[1,-2,3,5,-3,2]返回8 

数组：[0,-2,3,5,-1,2]返回9

数组：[-9,-2,-3,-5,-3]返回8

【解法一】

设Sum[i,...,j]为数组A中第i个元素到第j个元素的和(0<=i<=j<n),遍历所有的Sum[i,...,j]。

对每个整数对，我们都要计算x[i...j]的总和，并检验该总和是否大于迄今为止的最大总和。

/*********************************
*   日期：2014-5-19
*   作者：SJF0115
*   题目: 2.14 求数组的子数组之和的最大值
*   来源：编程之美
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <limits.h>
using namespace std;#define N 1001int array[N];int main(){int n,i,j,k,sum;//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);while(scanf("%d",&n) != EOF){//输入数据for(i = 0;i < n;i++){scanf("%d",&array[i]);}int maxSum = INT_MIN;// i 遍历数组起点 j 遍历数组终点for(i = 0;i < n;i++){for(j = i;j < n;j++){sum = 0;//遍历所有可能的Sum[i..j]for(k = i;k <= j;k++){sum += array[k];}maxSum = max(maxSum,sum);}}printf("%d\n",maxSum);}return 0;
}

时间复杂度为O（n^3）。程序运行速度很慢。

【解法二】

x[i...j]的总和与前面已经计算出的x[i...j-1]的总和密切相关，Sum[i..j] = Sum[i...j-1]+array[j] 则可以将上面算法中最后一个循环去掉，

避免重复计算，从而使算法得以改进。

时间复杂度为O（n^2）。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <limits.h>
using namespace std;#define N 1001int array[N];int main(){int n,i,j,k,sum;//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);while(scanf("%d",&n) != EOF){//输入数据for(i = 0;i < n;i++){scanf("%d",&array[i]);}int maxSum = INT_MIN;// i 遍历数组起点 j 遍历数组终点for(i = 0;i < n;i++){sum = 0;for(j = i;j < n;j++){sum += array[j];maxSum = max(maxSum,sum);}}printf("%d\n",maxSum);}return 0;
}

【解法三】

通过访问外循环执行之前就以构建好的数据结构的方式在内循环中计算总和。

即常见的前缀和技巧。令Sumi=A0+A1+A2+…+Ai，规定Sum0=A0，则可以在O(1)时间内求出子序列的值：Ai+Ai+1+…+Aj=Sumj-Sumi-1。这样，时间复杂度降为O(n2)。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;#define N 1001int array[N];
int sum[N];
int main(){int n,i,j;//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);while(scanf("%d",&n) != EOF){//输入数据for(i = 0;i < n;i++){scanf("%d",&array[i]);//计算前缀和if(i != 0){sum[i] = sum[i-1] + array[i];}else{sum[i] = array[i];}}int maxSum = sum[0];// i 遍历数组起点 j 遍历数组终点for(i = 0;i < n;i++){for(j = i+1;j < n;j++){maxSum = max(maxSum,sum[j] - sum[i]);}}printf("%d\n",maxSum);}return 0;
}

【解法四】 分治策略

如果将所给数组(A[0],...,A[n-1])分为长度相等的两段数组(A[0],...,A[n/2-1])和(A[n/2],...,A[n-1]),分别求出这两段数组各自最大子段和，则原数组(A[0],...,A[n-1])的最大子段和分为以下三种情况，要么在前半部分a中，要么在后半部分b中，要么跨越a和b之间的边界：
          a.(A[0],...,A[n-1])的最大子段和与(A[0],...,A[n/2-1])的最大子段和相同；
          b.(A[0],...,A[n-1])的最大子段和与(A[n/2],...,A[n-1])的最大子段和相同；
          c.(A[0],...,A[n-1])的最大子段跨过其中间两个元素A[n/2-1]到A[n/2].
对应a和b两个问题是规模减半的两个相同的子问题，可以用递归求得。
对于c,需要找到以A[n/2-1]结尾的和最大的一段数组和S1=(A[i],...,A[n/2-1])和以A[n/2]开始和最大的一段和S2=(A[n/2],...,A[j]),那么第三种情况的最大值为S1+S2。只需要对原数组进行一次遍历即可。在a中的部分是a中包含右边界的最大子数组，在b中的部分是b中包含左边界的最大子数组。

这其实是一种分治策略，时间复杂度为O（nlogn）。

/*********************************
*   日期：2014-5-20
*   作者：SJF0115
*   题目: 2.14 求数组的子数组之和的最大值
*   来源：编程之美
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;#define N 1001int array[N];int MaxSubsequence(int L,int R){int i,j;//0个元素if(L > R){return 0;}//1个元素if(L == R){return array[L];}int mid = (L + R) / 2;//跨越a和b之间的部分//在a中的部分是a中包含右边界的最大子数组int sum = 0;int leftMax = array[mid];for(i = mid;i >= L;i--){sum += array[i];leftMax = max(leftMax,sum);}//在b中的部分是b中包含左边界的最大子数组sum = 0;int rightMax = array[mid+1];for(i = mid+1;i <= R;i++){sum += array[i];rightMax = max(rightMax,sum);}//递归调用//跨越a和bint maxSum = rightMax+leftMax;//整个在a中maxSum = max(maxSum,MaxSubsequence(L,mid));//整个在b中maxSum = max(maxSum,MaxSubsequence(mid+1,R));return maxSum;
}int main(){int n,i,j;//freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);while(scanf("%d",&n) != EOF){//输入数据for(i = 0;i < n;i++){scanf("%d",&array[i]);}int maxSum = MaxSubsequence(0,n-1);printf("%d\n",maxSum);}return 0;
}


【解法五】

利用动态规划做题。

只遍历数组一遍，当从头到尾部遍历数组A， 遇到一个数有两种选择 （1）加入之前subArray （2）自己另起一个subArray

设状态S[i], 表示以A[i]结尾的最大连续子序列和，状态转移方程如下:

S[i] = max(S[i-1] + A[i],A[i])

时间复杂度：O(n)     空间复杂度：O(n)

【代码五】

    /*--------------------------------------------*   日期：2015-02-03*   作者：SJF0115*   题目: 53.Maximum Subarray*   网址：https://oj.leetcode.com/problems/maximum-subarray/*   结果：AC*   来源：LeetCode*   博客：-----------------------------------------------*/class Solution {public:int maxSubArray(int A[], int n) {int S[n];int maxSum = A[0];S[0] = A[0];// 动态规划for(int i = 1;i < n;i++){S[i] = max(S[i-1] + A[i],A[i]);if(S[i] > maxSum){maxSum = S[i];}//if}//forreturn maxSum;}};

【解法六】

对前一个方法继续优化，从状态转移方程上S【i】只与S【i-1】有关，与其他都无关，因此可以用一个变量来记住前一个的最大连续数组和就可以了。

这样就可以节省空间了。

时间复杂度：O(n)     空间复杂度：O(1)

【代码六】

    /*--------------------------------------------*   日期：2015-02-03*   作者：SJF0115*   题目: 53.Maximum Subarray*   网址：https://oj.leetcode.com/problems/maximum-subarray/*   结果：AC*   来源：LeetCode*   博客：-----------------------------------------------*/class Solution {public:int maxSubArray(int A[], int n) {int maxSum = A[0];// sum 记住前一个的最大连续数组和int sum = 0;// 动态规划for(int i = 0;i < n;i++){sum += A[i];sum = max(sum,A[i]);if(sum > maxSum){maxSum = sum;}//if}//forreturn maxSum;}};

【解法七】
时间复杂度：O(n)     空间复杂度：O(1) 

/*********************************
*   日期：2015-01-27
*   作者：SJF0115
*   题目: 53.Maximum Subarray
*   网址：https://oj.leetcode.com/problems/maximum-subarray/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <climits>
using namespace std;class Solution {
public:int maxSubArray(int A[], int n) {if(n <= 0){return 0;}//if// 最大和int max = A[0];// 当前最大和int cur = 0;for(int i = 0;i < n;++i){// 一旦当前最大和小于0就重置为0,一个负数只能使最大和变小if(cur < 0){cur = 0;}//ifcur += A[i];if(cur > max){max = cur;}//if}//forreturn max;}
};
int main(){Solution solution;int n = 9;int A[] = {-2,1,-3,4,-1,2,1,-5,4};int result = solution.maxSubArray(A,n);// 输出cout<<result<<endl;return 0;
}



【相似题目】

UVA之1121 - Subsequence

[LeetCode]53.Maximum Subarray






这篇关于编程之美之2.14 求数组的子数组之和的最大值的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/723341。

相关文章

零基础STM32单片机编程入门(一)初识STM32单片机

零基础STM32单片机编程入门(一)初识STM32单片机

文章目录 一.概要二.单片机型号命名规则三.STM32F103系统架构四.STM32F103C8T6单片机启动流程五.STM32F103C8T6单片机主要外设资源六.编程过程中芯片数据手册的作用1.单片机外设资源情况2.STM32单片机内部框图3.STM32单片机管脚图4.STM32单片机每个管脚可配功能5.单片机功耗数据6.FALSH编程时间，擦写次数7.I/O高低电平电压表格8.外设接口
阅读更多...
16.Spring前世今生与Spring编程思想

16.Spring前世今生与Spring编程思想

1.1.课程目标 1、通过对本章内容的学习,可以掌握Spring的基本架构及各子模块之间的依赖关系。 2、 了解Spring的发展历史，启发思维。 3、 对 Spring形成一个整体的认识，为之后的深入学习做铺垫。 4、 通过对本章内容的学习，可以了解Spring版本升级的规律，从而应用到自己的系统升级版本命名。 5、Spring编程思想总结。 1.2.内容定位 Spring使用经验
阅读更多...
剑指offer（C++）--数组中只出现一次的数字

剑指offer（C++）--数组中只出现一次的数字

题目 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 class Solution {public:void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {int len = data.size();if(len<2)return;int one = 0;for(int i
阅读更多...
BD错误集锦4——IDEA编程连接hbase失败，put操作一直没有通过，并且无异常信息

BD错误集锦4——IDEA编程连接hbase失败，put操作一直没有通过，并且无异常信息

参考文章：https://blog.csdn.net/ZJ18712852367/article/details/81938524
阅读更多...
IPython小白教程：提升你的Python交互式编程技巧，通俗易懂！

IPython小白教程：提升你的Python交互式编程技巧，通俗易懂！

IPython是一个增强的Python交互式shell，它提供了丰富的功能和便捷的交互方式，使得Python开发和数据分析工作更加高效。本文将详细介绍IPython的基本概念、使用方法、主要作用以及注意事项。 一、IPython简介 1. IPython的起源 IPython由Fernando Pérez于2001年创建，旨在提供一个更高效的Python交互式编程环境。 2. IPyt
阅读更多...
IOS 数组去重的几种方式

IOS 数组去重的几种方式

本来只知道NSSet和KeyValues的。今天又新学了几种方式 还有就是和同事学的一种方式 外层循环从0开始遍历，内层从最后一个元素开始遍历 for(int i=0;i<index;i++){  for(int j=index-1;j>i;j-- ){ } }
阅读更多...
从《深入设计模式》一书中学到的编程智慧

从《深入设计模式》一书中学到的编程智慧

软件设计原则   优秀设计的特征   在开始学习实际的模式前，让我们来看看软件架构的设计过程，了解一下需要达成目标与需要尽量避免的陷阱。 代码复用 无论是开发何种软件产品，成本和时间都最重要的两个维度。较短的开发时间意味着可比竞争对手更早进入市场; 较低的开发成本意味着能够留出更多营销资金，因此能更广泛地覆盖潜在客户。 代码复用是减少开发成本时最常用的方式之一。其意图
阅读更多...
Java基础（二）——数组，方法，方法重载

Java基础（二）——数组，方法，方法重载

个人简介 👀个人主页： 前端杂货铺 ⚡开源项目： rich-vue3 （基于 Vue3 + TS + Pinia + Element Plus + Spring全家桶 + MySQL） 🙋‍♂️学习方向： 主攻前端方向，正逐渐往全干发展 📃个人状态： 研发工程师，现效力于中国工业软件事业 🚀人生格言： 积跬步至千里，积小流成江海 🥇推荐学习：🍖开源 rich-vue3 🍍前端面试
阅读更多...
Java并发编程—阻塞队列源码分析

Java并发编程—阻塞队列源码分析

在前面几篇文章中，我们讨论了同步容器(Hashtable、Vector），也讨论了并发容器（ConcurrentHashMap、CopyOnWriteArrayList），这些工具都为我们编写多线程程序提供了很大的方便。今天我们来讨论另外一类容器：阻塞队列。 　　在前面我们接触的队列都是非阻塞队列，比如PriorityQueue、LinkedList（LinkedList是双向链表，它实现了D
阅读更多...
剑指offer—编程题7（用两个栈实现一个队列）

剑指offer—编程题7（用两个栈实现一个队列）

题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail 和deleteHead，分别完成在队列尾部插入结点和在队列头部删除结点的功能。 代码如下： [java]  view plain copy print ? public class Test07 {       /**       * 用两个栈模拟的队列       *
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2