LeetCode-053-最大子序和
2021/7/3 23:21:49
本文主要是介绍LeetCode-053-最大子序和,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最大子序和
题目描述:给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例说明请见LeetCode官网。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-subarray/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法一:动态规划
首先,初始化max和sum都为nums的第一个元素的值,然后从第2位开始遍历数组:
- 当
sum <= 0
时,sum设置为当前索引为的值,也就是抛弃之前累加的值;- 当
sum > 0
时,sum加上当前索引位的值,累加;- 然后每次便利时max取max和sum的较大者。
最后,返回max即为最后结果。
public class LeetCode_053 { public static int maxSubArray(int[] nums) { int max = nums[0], sum = nums[0]; for (int i = 1; i < nums.length; i++) { if (sum <= 0) { sum = nums[i]; } else { sum = sum + nums[i]; } max = Math.max(max, sum); } return max; } public static void main(String[] args) { int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}; System.out.println(maxSubArray(nums)); } }
【每日寄语】 在忙碌的日子里,要学会每天给自己找一个开心的理由,哪怕只是,阳光很暖,电量很满。
这篇关于LeetCode-053-最大子序和的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解