Implement Maximum Subarray Sum with dynamic programming.

How to implement Maximum Subarray Sum with dynamic programming?

In this case array also have negative elements otherwise the answer would have simply been the sum of entire array.

In this solution dp[i] stores the maximum among all the sum of all the sub arrays ending at index i. And then we can return maximum of this array dp as the answer.

We have maintained the value of maximum sum in variable so we do not need to find maximum element in dp array separately.

int solveUsingDp(int a[],int n){
    int dp[]=new int[n];
    dp[0]=a[0];
    int big=dp[0];
    for (int i = 1; i < n; i++) {
        dp[i]=max(dp[i-1]+a[i],a[i]);
        if (dp[i]>big)big=dp[i];
    }
    return big;
}

Do write the comments if you face any difficulty.

2 Likes

is its time complexity 0(n) ?

1 Like

@rashedcs

Off course yes.

You need to traverse entire array only once and hence complexity is O(n);

This is one of a clasic dp problem. The key thing to notice here is that if dp[i] means that it is the sum of the largest possible subarray ending with a[i] then d[i] will either be a[i](it means that the subarray starts from here) or it will continue the subarray which ended at dp[i-1].
so it will be max(dp[i-1]+a[i],a[i]) or you can also write it as if dp[i-1] is positive then dp[i] = dp[i-1] + a[i] else a[i].
Hope that helped. for a detailed explanation you can check this - https://www.youtube.com/watch?v=ohHWQf1HDfU

My code -

int max_subarr_sum(int a[], int n){
    int dp[n];
    dp[0] =a[i];
    int ans = dp[0];
    for (int i = 1; i < n; i++){
       dp[i] = dp[i-1] > 0?dp[i-1]+a[i]:a[i];
       ans = max(ans,dp[i]);
    }
    return ans;
}

Tnq u @mathecodician

Not mocking you but atleast you should show the people that you have done some research/trial on your own.Simply putting question like how to implement XYZ or how to do XYZ won’t be the best for you.Put some code that you have tried and what error you got while implementing that.No one is here for spoon feeding buddy.

//