【算法】LeetCode算法题-Maximum Subarray

作者 : 开心源码 本文共1591个字,预计阅读时间需要4分钟 发布时间: 2022-05-13 共248人阅读

这是悦乐书的第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

本次解题使用的开发工具是eclipse,jdk使用的版本是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 小结

今天此题涉及的分而治之算法,会写在后面的算法和数据结构的理论知识详情中,研究透彻了再和各位分享。以上就是一律内容,假如大家有什么好的解法思路、建议或者者其余问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 【算法】LeetCode算法题-Maximum Subarray

发表回复