最大子段和0004

2024-04-13 11:48

文章标签 最大子段 0004

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

文章目录

1、描述
2、思路
4、notes
6、code

1、描述

53,面试题42，给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

2、思路

dp
找dp数组，

4、notes

买股票的链接，只能交易一次

6、code

//1暴力，就是直接遍历两边就好了
class Solution {
public:int maxSubArray(vector<int>& nums) {int max=nums[0];  //假定最大子段和是第一个元素int ide=nums.size();   //得到数组长度for(int i=0;i<ide;i++)  {int sum=0;             //一层一个sumfor(int j=i;j<ide;j++){sum +=nums[j];if(sum>max)       //如果大于现存最大的，就更新{max=sum;     //更新}}}return max;}
};

dp方式1

class Solution {
public:int maxSubArray(vector<int>& nums) {int res=nums[0];  //假定最大子段和是第一个元素int n=nums.size();   //得到数组长度vector<int>dp(n,nums[0]);for(int i=1;i<n;i++)  {dp[i]=nums[i]+max(dp[i-1],0);  // 如果之前的和是负数，那么当前dp的值就是nums[i]res=max(dp[i],res);}return res;}
};

dp方式2:

class Solution {
public:int maxSubArray(vector<int>& nums) {int n=nums.size();int res=nums[0];vector<int>dp(n,INT_MIN);  // 构造dp数组dp[0]=nums[0];for(int i=1;i<n;i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);if(res<dp[i])res=dp[i];}return res;}
};

//2分治：

递归的时候两边分开，然后中间的从mid开始往两边加，取出来最大的半边字串，返回时，把左右加起来就好了
class Solution {
public:int maxSubArray(vector<int>& nums) {int result=INT_MIN;         //初始化为int最小值int ide=nums.size();           //获取数组长度result=getResult(nums,0,ide-1);  //重定义一个函数，参数是数组名，前后座标return result;}int getResult(vector<int>& nums,int left,int right)  //递归函数（数组名，左边，右边）{if(left==right)          //如果相等就是分到最后了return nums[left];int mid=(left+right)/2;   int leftResult=getResult( nums, left, mid);  //左边递归int rightResult=getResult( nums, mid+1, right);  //右边递归，注意是mid+1int midResult=getMidResult(nums, left, right, mid);  //中间的再定义一个函数int result=max(leftResult,rightResult);               //3个值取最大，用两次maxresult=max(result,midResult);return result;}int getMidResult(vector<int> &nums,int left,int right,int mid)  //中间求最大，用4个参数的函数{int leftMax=INT_MIN;int Sum=0;for(int i=mid;i>=left;i--)     //从中间往左累加，记录遍历过程中最大的那个{Sum+=nums[i];leftMax=max(leftMax,Sum);}int rightMax=INT_MIN;Sum=0;                           //左边用过这个Sum变量之后，归0后在右边重新用for(int i=mid+1;i<=right;i++)  //从中间往右累加，记录遍历过程中最大的那个{Sum+=nums[i];rightMax=max(rightMax,Sum);}return rightMax+leftMax;}
};