Two O(n) C++ solution


  • 0
    C
    class Solution {
    public:
    /**method one**//*
        int maxSubArray(vector<int>& nums) {
            int max = INT_MIN;
            bool hasZero = false;
            bool hasPos = false;
            for(int i=0;i<nums.size();++i){
                if(max<nums[i]) max = nums[i];
                if(nums[i]==0) hasZero = true;
                if(nums[i]>0) hasPos = true;
            }
            int res = 0,tem = 0;
            for(int i=0;i<nums.size();++i){
                tem += nums[i];
                if(tem<0) tem = 0;
                if(tem>res) res = tem;
            }
            if(res==0&&!hasPos&&!hasZero){
                res = max;
            }
            return res;
        }
    */
    /**method two dp**/
        int maxSubArray(vector<int>& nums) {
            if(nums.empty()) return 0;
            int sum[nums.size()];
            int max[nums.size()];
            sum[0] = max[0] = nums[0];
            for(int i=1;i<nums.size();++i){
                sum[i] = sum[i-1]<0?nums[i]:sum[i-1]+nums[i];
                max[i] = max[i-1]>sum[i]?max[i-1]:sum[i];
            }
            return max[nums.size()-1];
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.