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.
The Maximum Subarray
The Maximum Subarray
+ 0 comments Link of the Maximum Subarray problem explanation (Hindi) and code in Python3: https://youtu.be/Hlw2rd7eNE8
+ 0 comments def max_subarray(A): max_ending_here = max_so_far = 0 for x in A: max_ending_here = max(0, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far
+ 0 comments This is my javascript Solution
function maxSubarray(arr) { let result = 0, subseq_sum = 0, subarr_sum = 0; arr.forEach((data) => { subseq_sum += data; if(data > 0) subarr_sum += data; if(result < subseq_sum) result = subseq_sum; if(subseq_sum < 0) subseq_sum =0; }) if(result === 0) { return [Math.max(...arr), Math.max(...arr)]; } else { return [result, subarr_sum]; } }
+ 0 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./* 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 p the 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 if tmp_j = arr[j] is larger or tmp_j = sum(arr[i*..j-1]) + arr[j] is larger. we now can relate dp[j] to dp[j-1], as follow dp[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 easily by 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) { long dp = 0; long max_dp = numeric_limits<long>::min(); long subseq = 0; long maxarrj = numeric_limits<long>::min(); for (long arrj : 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)}; }
+ 0 comments /* The key to this one is that you want to do one pass through the data. I first did a substring inner loop for the max subarray sum (code in comments), but this timed out for one test. int subArraySum = 0; for (int j = i; j < arr.size(); j++) { subArraySum += arr.get(j); if (greatestSum == null || subArraySum > greatestSum) { greatestSum = subArraySum; } } } results.add(greatestSum); */ public static List<Integer> maxSubarray2(List<Integer> arr) { List<Integer> results = new ArrayList<Integer>(); int subArraySum = 0; int sumSubSequence = 0; int subArraySumMax = 0; for (int i = 0; i < arr.size(); i++) { //this is to get the max subarray sum subArraySum += arr.get(i); if(subArraySum < 0) { subArraySum = 0; } subArraySumMax = Math.max(subArraySumMax, subArraySum); //this is to get the max subsequence sum Integer value = arr.get(i); if (value > 0) { sumSubSequence += value; } } if (sumSubSequence > 0) { results.add(subArraySumMax); results.add(sumSubSequence); } else { //there are no positive values so we pick the highest value final int max = Collections.max(arr); results.add(max); results.add(max); } return results; }
Load more conversations
Sort 478 Discussions, By:
Please Login in order to post a comment