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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Maximum Subarray
  5. Discussions

The Maximum Subarray

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 478 Discussions, By:

recency

Please Login in order to post a comment

  • raghuvanshi_dev1
    3 days ago+ 0 comments

    Link of the Maximum Subarray problem explanation (Hindi) and code in Python3: https://youtu.be/Hlw2rd7eNE8

    0|
    Permalink
  • genewangtp
    7 days ago+ 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|
    Permalink
  • Dev_SoNB
    4 weeks ago+ 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|
    Permalink
  • wilsonthongwk
    1 month ago+ 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|
    Permalink
  • srmckenna
    2 months ago+ 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;
        }
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy