当前位置:网站首页>LeetCode_ 53 (maximum subarray and)
LeetCode_ 53 (maximum subarray and)
2022-07-01 04:44:00 【***】
Title Description : Give you an array of integers nums , Please find a continuous subarray with the largest sum ( A subarray contains at least one element ), Return to its maximum and .
A subarray is a continuous part of an array .
Example 1:
Input :nums = [-2,1,-3,4,-1,2,1,-5,4]
Output :6
explain : Continuous subarray [4,-1,2,1] And the biggest , by 6 .
Example 2:
Input :nums = [1]
Output :1
Example 3:
Input :nums = [5,4,-1,7,8]
Output :23
Tips :
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Method 1 : Divide and conquer method ( recursive )
class Solution {
/**
* Transition method
* @param nums Original array
* @return Returns the largest subsegment and
*/
public static int maxSubArray(int[] nums) {
return MaxSubArray(nums,0,nums.length-1);
}
/**
* Find the largest subsegment and
* @param nums Array to be found
* @param left Left pointer
* @param right Right pointer
* @return Maximum sub sum
*/
public static int MaxSubArray(int[] nums,int left,int right) {
int res=0,leftsum,rightsum,midsum,center;
int sum1,sum2,leftsum1,rightsum1;
if(left==right){
// Recursion end condition
res=nums[left]; // Recurse until there is only one element left in the sub segment , Then the maximum sum of sub segments is the element
}else{
center=(left+right)/2; // Take the middle element and divide the array into two segments , Divide and rule
leftsum=MaxSubArray(nums,left,center);// Recursively find the sum of the largest sub segments on the left
rightsum=MaxSubArray(nums,center+1,right);// Recursively find the sum of the largest sub segments on the right
sum1=-1230000000;leftsum1=0;// hypothesis sum1 For a very small number , Find the left maximum sub segment sum
for (int i = center; i >=left ; i--) {
leftsum1+=nums[i];
if(leftsum1>sum1)sum1=leftsum1;
}
sum2=-1230000000;rightsum1=0;// hypothesis sum2 For a very small number , Find the sum of the right largest subsegments
for (int i = center+1; i <=right ; i++) {
rightsum1+=nums[i];
if(rightsum1>sum2)sum2=rightsum1;
}
midsum=sum1+sum2;
int s;
if(leftsum>rightsum)s=leftsum;
else s=rightsum;
if(s>midsum)res=s;
else res=midsum;
}
return res;
}
}
Method 2 、 Dynamic programming
边栏推荐
- LeetCode_28(实现 strStr())
- The junior college students were angry for 32 days, four rounds of interviews, five hours of soul torture, and won Ali's offer with tears
- Dual contractual learning: text classification via label aware data augmentation reading notes
- OdeInt與GPU
- 解决qiankun中子应用外链文件无法获取
- 如何看待智慧城市建设中的改变和机遇?
- Kodori tree board
- [2020 overview] overview of link prediction based on knowledge map embedding
- Odeint et GPU
- 【FTP】FTP常用命令,持续更新中……
猜你喜欢
STM32 光敏电阻传感器&两路AD采集
2022 question bank and answers for safety production management personnel of hazardous chemical production units
How to use maixll dock
VR线上展览所具备应用及特色
神经网络-非线性激活
Kodori tree board
2022年化工自动化控制仪表操作证考试题库及答案
2022 a special equipment related management (elevator) simulation test and a special equipment related management (elevator) certificate examination
2022年上海市安全员C证考试题模拟考试题库及答案
Maixll dock quick start
随机推荐
Advanced application of ES6 modular and asynchronous programming
Execution failed for task ‘:app:processDebugResources‘. > A failure occurred while executing com. and
(12) Somersault cloud case (navigation bar highlights follow)
C -- array
Pytorch(二) —— 激活函数、损失函数及其梯度
Registration for R2 mobile pressure vessel filling test in 2022 and R2 mobile pressure vessel filling free test questions
2022 Shanghai safety officer C certificate examination question simulation examination question bank and answers
All in all, the low code still needs to solve these four problems
Research on medical knowledge atlas question answering system (I)
Basic usage, principle and details of session
Offline installation of Wireshark 2.6.10
LeetCode_66(加一)
JS image path conversion Base64 format
JVM栈和堆简介
C - detailed explanation of operators and summary of use cases
Question bank and answers for chemical automation control instrument operation certificate examination in 2022
Why is Internet thinking not suitable for AI products?
Shell analysis server log command collection
Applications and features of VR online exhibition
Pytorch(三) —— 函数优化