C++ O(N) Solution with dynamic programming


  • 0
    M

    We can use dynamic programming to solve this problem. When we see the problem first, it's easy to find the recursion equation as below: sum[i] = max{sum[i-1]+a[i],a[i]}. The sum[i] recorded the value of the largest subsequence ending in index i. However, it's easy to use a extra value to replace the whole array as below:

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int b=0,sum=nums[0];
            for(int i=0;i<nums.size();i++){
                if(b>0)
                    b+=nums[i];
                else
                    b=nums[i];
                sum=max(sum,b);
            }
            return sum;
        }
    };
    

Log in to reply
 

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