申请完域名如何建设网站,知名的网页制作公司推荐,秒拍wordpress插件,简单网页贪心算法理论基础#xff1a; 局部最优推全局最优 贪心无套路~ 没有什么规律~ 重点#xff1a;每个阶段的局部最优是什么#xff1f; 题目描述#xff1a; 给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#… 贪心算法理论基础 局部最优推全局最优 贪心无套路~ 没有什么规律~ 重点每个阶段的局部最优是什么 题目描述 给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 子数组 是数组中的一个连续部分。 解题思路贪心算法详细思路在注释中有~ 代码实现 class Solution {/*** 解题思路贪心算法当 加上一个数发现比当前连续和(sum)要小的时候直接舍掉就从下一个正数重新开始计算* 注意连续和是负数的时候丢弃而不是遇到负数就丢弃* 暴力法时间复杂度 O(n^2)* 贪心算法时间复杂度 O(n)*/public int maxSubArray(int[] nums) {int len nums.length;int sum 0;// 连续和int maxSubSum Integer.MIN_VALUE;// 最大连续和for (int i 0; i len; i) {sum nums[i];if (sum maxSubSum){maxSubSum sum;}if (sum 0){sum 0;// 更新 sum0}}return maxSubSum;}
}
