We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
here is a dp solution with time complexity of O(N). the dp reasoning is also provided in the comment, which may be reusable in some other dp problems.
/*denote dp[j] is the max sum of any sub-array in arr[0...j] ending at arr[j].consider the sub-problem of dp[j]. how does it relate to dp[j-1]?given dp[j-1], it corresponds to sum(arr[i*..j-1]) for some optimal i*now consider tmp_j = sum(arr[p..j-1]) + arr[j].find the p* such that the corresponding tmp_j* is the maximum over all pthe tmp_j consists of two parts, - the sum(arr[p..j-1]) part is obviously maximum when p = i*- arr[j] part is fixed.thus we only have to compare iftmp_j = arr[j] is larger ortmp_j = sum(arr[i*..j-1]) + arr[j] is larger.we now can relate dp[j] to dp[j-1], as followdp[j] = max(arr[j], dp[j-1] + arr[j])initially,dp[-1] = 0 the max sub-array in arr[0..N-1] is dp[j*] and j* can be found easilyby looking into the dp[0..N-1]. the max-sequence of arr[:] is simply the sum of all non-negative values of arry[:]. if all values are negative, max-sequence contains only the max value.*/vector<int>maxSubarray(vector<int>arr){longdp=0;longmax_dp=numeric_limits<long>::min();longsubseq=0;longmaxarrj=numeric_limits<long>::min();for(longarrj:arr){dp=max(arrj,dp+arrj);max_dp=max(dp,max_dp);subseq+=max(0l,arrj);maxarrj=max(maxarrj,arrj);}return{(int)max_dp,(int)(subseq>0?subseq:maxarrj)};}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Maximum Subarray
You are viewing a single comment's thread. Return to all comments →
here is a dp solution with time complexity of
O(N)
. the dp reasoning is also provided in the comment, which may be reusable in some other dp problems.