Leetcode83: Maximum Subarray

2024-08-28 19:48
文章标签 maximum subarray leetcode83

本文主要是介绍Leetcode83: Maximum Subarray,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.

现在对线性时间解法做一下解释,属于一种DP问题。已知了前k个元素的最大子序列和为maxSub(已经被记录下来了),以及一个临时和sum,如果添加了第k+1这个元素,由于是连续子序列这个限制,所以如果k+1这个元素之前的和是小于0的,那么对于增大k+1这个元素从而去组成最大子序列是没有贡献的,所以可以把sum 置0。举个例子,-1, -2 ,4, -5, 7这里假定7为第k+1个元素,那么很明显可以看出,之前的sum = -5 + 4 =-1,那么这样对于7来说只会减少它,所以直接置sum = 0, 0 + 7才能得到正确的答案。再拓展这个数组, -1, -2, 4, -5, 7, 1 这里1之前的sum = 7 > 0,对于后面的1来组成最大子序列是有贡献的,所以sum = 7 + 1 =8。再注意一点,只要sum不减到负数,中间出现小于0的元素是没关系的,sum仍然可以继续累加。

class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();if(n==0)return 0;int maxsum = nums[0];int sum = nums[0];for(int i = 1; i < n; i++){if(sum < 0)sum = 0;sum += nums[i];maxsum = max(sum, maxsum); }return maxsum;}
};


这篇关于Leetcode83: Maximum Subarray的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1115717

相关文章

leetcode#628. Maximum Product of Three Numbers

题目 Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1: Input: [1,2,3]Output: 6 Example 2: Input: [1,2,3,4]Output: 24 Note: The lengt

Maximum likelihood function maximizes what thing?

最大似然函数(Maximum Likelihood Function)最大化的是数据在给定参数下出现的概率。具体来说,它最大化的是似然函数(Likelihood Function),即给定参数 ( \theta ) 下观测数据的概率。在统计学中,似然函数 ( L(\theta) ) 通常定义为所有独立观测数据点概率的乘积,对于参数 ( \theta ) 的函数。 对于一组独立同分布的观测数据

ORA-24067: exceeded maximum number of subscribers for queue ADMIN.SMS_MT_QUEUE

临时处理办法: delete from aq$_ss_MT_tab_D;delete from aq$_ss_MT_tab_g;delete from aq$_ss_MT_tab_h;delete from aq$_ss_MT_tab_i;delete from aq$_ss_MT_tab_p;delete from aq$_ss_MT_tab_s;delete from aq$

[LeetCode] 239. Sliding Window Maximum

题:https://leetcode.com/problems/sliding-window-maximum/description/ 题目 Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You

vue3 el-menu 菜单Maximum recursive updates exceeded 报错

vue3 用el-menu实现管理后台左侧菜单,报Uncaught (in promise) Maximum recursive updates exceeded in component <ElMenu>. This means you have a reactive effect that is mutating its own dependencies and thus recursivel

浙大数据结构:01-复杂度2 Maximum Subsequence Sum

数据结构MOOC PTA习题 01-复杂度2 Maximum Subsequence Sum #include <iostream>using namespace std;const int M = 100005;int a[M];int main(){int k;cin >> k;int f = 1;for (int i = 0; i < k; i++){cin >> a[i

Maximum Index

Given an array arr[], find the maximum j – i such that arr[j] > arr[i] Given an array arr[], find the maximum j – i such that arr[j] > arr[i]. Examples: Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}O

Maximum Number in Mountain Sequence

Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top. Example Example 1: Input: nums = [1, 2, 4, 8, 6, 3] Output: 8 Example 2: Input: nums = [

Maximum Depth of N-ary Tree

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]Output: 5 思路1:DFS ,divide and conquer /*// Definition for a Node.class Node {public int v

Subarray Sum Equals K

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1: Input:nums = [1,1,1], k = 2Output: 2 思路:用prefixsum prefixsu