临沂网站开发技术员,搜狐酒业峰会,多平台发布工具,惠东网站开发这是悦乐书的第154次更新#xff0c;第156篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第13题#xff08;顺位题号是53#xff09;。给定一个整数数组nums#xff0c;找出一个最大和#xff0c;此和是由数组中索引连续的元素组成#xff0c;至少包含一个…这是悦乐书的第154次更新第156篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第13题顺位题号是53。给定一个整数数组nums找出一个最大和此和是由数组中索引连续的元素组成至少包含一个元素。例如 输入[-2, 1, -3, 4, -1, 2, 1, -5,4] 输出6 说明[4-1,2,1]具有最大的和为6 输入[1, 2, 3] 输出6 说明[1, 2, 3]具有最大的和为6 本次解题使用的开发工具是eclipsejdk使用的版本是1.8环境是win7 64位系统使用Java语言编写和测试。 02 第一种解法 因为本题最后输出的是最大值所以需要进行求和并且要从第一位元素开始依次和相邻元素相加来判断。 第一次循环得到数组第一个元素与0相加此时最大值是元素本身。 第二次循环得到数组第二个元素与第一个元素相加此时相加的和需要先判断是否大于第二个元素本身因为如果两个数的和还没有本身大那么此时最大和就是第二个元素本身。其次还要和上一个和判断如果大于第一次循环得到的和那么新的最大和即为第一个元素和第二个元素之和或者第二个元素本身反之最大和依旧是第一次循环后的最大和。 后面的循环与上面一致最开始第一次的循环也是如此为了方便对比只是详细说明了第二次循环的处理逻辑。 public int maxSubArray(int[] nums) {int sum 0;int max Integer.MIN_VALUE;for (int i 0; i nums.length; i) {sum nums[i];if (nums[i] sum) {sum nums[i];}if (sum max) {max sum;}}return max;
} 对于上面的代码我们还可以再简化下。 public int maxSubArray2(int[] nums) {int result Integer.MIN_VALUE;int sum 0;for (int i 0; i nums.length; i) {sum Math.max(nums[i] sum, nums[i]);result Math.max(result, sum);}return result;
} 03 第二种解法 还有一种思路就是分而治之将大问题拆分成小问题找到小问题的答案后最后合在一起再得出最后的答案。下面的代码是讨论区里某位大神的可以好好看下。 public int maxSubArray3(int[] a) {return helper(a, 0, a.length - 1);
}int helper(int[] a, int l, int r) {if(l r) return Integer.MIN_VALUE;if(l r) return a[l];int mid l (r - l)/2;return Math.max(crossMidMax(a, l, r), Math.max(helper(a, l, mid - 1), helper(a, mid 1, r)));
}int crossMidMax(int[] a, int l, int r) {int mid l (r - l)/2;int lmax a[mid], lg a[mid];for(int i mid -1; i l; i--) {lmax a[i];lg Math.max(lmax, lg);}int rmax a[mid], rg a[mid];for(int i mid 1; i r; i) {rmax a[i];rg Math.max(rmax, rg);}return lg rg - a[mid];
} 04 小结 今天此题涉及的分而治之算法会写在后面的算法和数据结构的理论知识介绍中研究透彻了再和各位分享。以上就是全部内容如果大家有什么好的解法思路、建议或者其他问题可以下方留言交流点赞、留言、转发就是对我最大的回报和支持 转载于:https://www.cnblogs.com/xiaochuan94/p/9864536.html
