LeetCode-53. 最大子序和

题目描述 [最大子序和]

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

解题思路

  • 令temp为当前最大数组的和,num_max为最后返回的最大数组和
  • 从前往后扫描,对于第i个元素有两种选择:加入前面找到的子数组,作为新数组的第一个元素
    • 如果temp+a[i] > a[i],则令temp=temp+a[i];
    • 否则为temp重新赋值,temp=a[i];
  • 比较当前最大数值和与最大数组和
    即:
    temp = max(temp+a[i], a[i]);
    num_max = max(num_max, temp);

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int temp = 0;
        int num_max = INT_MIN;
        for(auto num:nums){
            temp = max(num, temp+num);
            num_max = max(num_max, temp);
        }
        return num_max;
    }
};
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容