最大子序和环形子数组最大和(Java,动态规划)
2021/10/6 11:11:00
本文主要是介绍最大子序和环形子数组最大和(Java,动态规划),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最大子序和
https://leetcode-cn.com/problems/maximum-subarray/
思路:
使用动态规划思想,在这里我使用一个temp表示当前的和,max表示最大值
代码如下:
if(nums.length==0)return 0; if(nums.length==1)return nums[0]; int temp=nums[0]; int sum=nums[0]; for (int i = 1; i < nums.length; i++) { temp=Math.max(temp+nums[i],nums[i]); if(temp>sum){ sum=temp; } } return sum;
环形子数组最大和
环形和普通的子数组最大和其实思路相似,我们的思路为:
分为两种情况
1.最大值为常规的子序列和不包括环 eg:-1 -2 3 -4
2.包括环 eg:[5,-4,5] 此时可用数组总和-连续的最小子序列和(不成环) 即为最大子序和。
有一种情况:当数组中全为负数 ,两个相减为0 ,这时候我们选择数组中最大的数。
选择这两种情况中的最大值,即为我们需要求的。
if(nums.length==0)return 0; if(nums.length==1)return nums[0]; int atemp=nums[0]; int itemp=nums[0]; int maxSum=nums[0]; int minSum=nums[0]; int sum=nums[0]; for (int i = 1; i < nums.length; i++) { atemp=Math.max(atemp+nums[i],nums[i]); itemp=Math.min(itemp+nums[i],nums[i]); if(maxSum<atemp){ maxSum=atemp; } if(minSum>itemp){ minSum=itemp; } sum+=nums[i]; } //说明数组中全为负数 返回最小的一个数 int s=0; if(sum-minSum==0){ Arrays.sort(nums); s=nums[nums.length-1]; } return Math.max(maxSum,sum-minSum==0?s:sum-minSum);
这篇关于最大子序和环形子数组最大和(Java,动态规划)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南