41. 最大子数组

xiaoxiao2021-02-28  35

提示

        LintCode中的相关算法题实现代码,可以在我的GitHub中下载。

题目需求

描述

        

给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。

    样例

        给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为6

    挑战

        

要求时间复杂度为O(n)

解题思路

    利用动态规划,我们这里使用一个数组保存每一个阶段的和。这里主要的步骤是:

        1.如果一个元素大于这个元素和前面的和,那么就保存这个元素,否者保存这个元素和前面的和的和。

    解决动态规划的主要思路是找出初始状态和转化方程式,这里的主要转化方程式是

    f(x)=max{a[i],a[I]+b[i-1]},这里b数组表示下标I-1的和。

实现代码

class Solution { public: /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ int maxSubArray(vector<int> &nums) { // write your code here if(nums.size()==0) return 0; vector<int> tmp; tmp.push_back(nums[0]); for(int i=1;i<nums.size();i++) { if(nums[i]+tmp[i-1]>nums[i]) { tmp.push_back(nums[i]+tmp[i-1]); } else { tmp.push_back(nums[i]); } } int sum=tmp[0]; for(int i=1;i<tmp.size();i++) { if(tmp[i]>sum) { sum=tmp[i]; } } return sum; } };
转载请注明原文地址: https://www.6miu.com/read-1950264.html

最新回复(0)