当前位置:网站首页>February 13, 2022 - Maximum subarray and
February 13, 2022 - Maximum subarray and
2022-07-06 10:36:00 【Procedural ape does not lose hair 2】
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 .
Subarray Is a continuous part of the 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 <= 10^5
-10^4 <= nums[i] <= 10^4
java Code :
class Solution {
public int maxSubArray(int[] nums) {
// int pre = 0, maxAns = nums[0];
// for (int x : nums) {
// pre = Math.max(pre + x, x);
// maxAns = Math.max(maxAns, pre);
// }
// return maxAns;
// Dynamic programming , Record dp[i] Record from 0 To i The largest substring of
int[] dp = new int[nums.length];
dp[0] = nums[0];
int maxAns = nums[0];
for(int i=1;i<nums.length;i++) {
dp [i] = Math.max(nums[i], dp[i-1]+nums[i]);
maxAns = Math.max(maxAns, dp[i]);
}
return maxAns;
}
}
边栏推荐
- Const decorated member function problem
- MySQL storage engine
- The governor of New Jersey signed seven bills to improve gun safety
- MySQL实战优化高手05 生产经验:真实生产环境下的数据库机器配置如何规划?
- MySQL Real Time Optimization Master 04 discute de ce qu'est binlog en mettant à jour le processus d'exécution des déclarations dans le moteur de stockage InnoDB.
- PyTorch RNN 实战案例_MNIST手写字体识别
- Software test engineer development planning route
- Mysql32 lock
- 实现以form-data参数发送post请求
- Google login prompt error code 12501
猜你喜欢
解决在window中远程连接Linux下的MySQL
使用OVF Tool工具从Esxi 6.7中导出虚拟机
A necessary soft skill for Software Test Engineers: structured thinking
实现微信公众号H5消息推送的超级详细步骤
保姆级手把手教你用C语言写三子棋
Bytetrack: multi object tracking by associating every detection box paper reading notes ()
Ueeditor internationalization configuration, supporting Chinese and English switching
Implement sending post request with form data parameter
Download and installation of QT Creator
Not registered via @EnableConfigurationProperties, marked(@ConfigurationProperties的使用)
随机推荐
MySQL ERROR 1040: Too many connections
Export virtual machines from esxi 6.7 using OVF tool
Redis集群方案应该怎么做?都有哪些方案?
MySQL29-数据库其它调优策略
百度百科数据爬取及内容分类识别
使用OVF Tool工具从Esxi 6.7中导出虚拟机
How to change php INI file supports PDO abstraction layer
MySQL实战优化高手03 用一次数据更新流程,初步了解InnoDB存储引擎的架构设计
MySQL34-其他数据库日志
Software test engineer development planning route
Super detailed steps for pushing wechat official account H5 messages
软件测试工程师必备之软技能:结构化思维
MySQL combat optimization expert 05 production experience: how to plan the database machine configuration in the real production environment?
Introduction tutorial of typescript (dark horse programmer of station B)
Implement context manager through with
评估方法的优缺点
Mysql28 database design specification
Mysql25 index creation and design principles
Mysql26 use of performance analysis tools
Time complexity (see which sentence is executed the most times)