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.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Maximum Subarray
  5. Discussions

The Maximum Subarray

Sort by

recency

|

492 Discussions

|

  • agentkaumal88
     + 0 comments

    C#

    public static List<int> maxSubarray(List<int> arr)
{
    if (arr.Count == 1)
    {
        return new List<int>() { arr[0], arr[0] };
    }

    var result = new List<int>();

    var isAllNegative = arr[0] < 0;
    var positiveSum = Math.Max(0, arr[0]);
    var minNegative = arr[0] < 0 ? arr[0] : -1 * int.MaxValue;

    var currentSubarrayMax = arr[0];
    var maxSoFar = arr[0];

    for (int i = 1; i < arr.Count; ++i)
    {
        // maximum subsequence sum
        if (arr[i] >= 0)
        {
            positiveSum += arr[i];

            if (isAllNegative)
            {
                isAllNegative = false;
            }
        }

        if (isAllNegative)
        {
            minNegative = Math.Max(minNegative, arr[i]);
        }

        // maximum subarray sum
        currentSubarrayMax = Math.Max(arr[i], currentSubarrayMax + arr[i]);
        maxSoFar = Math.Max(maxSoFar, currentSubarrayMax);
    }

    result.Add(maxSoFar);
    result.Add(isAllNegative ? minNegative : positiveSum);

    return result;
}

  • amitv28242
     + 0 comments

    java8

    java 8 beginner way

int sum=0;

   int max=arr.get(0);
   for(int i=0;i<arr.size();i++){
       sum+=arr.get(i);
       max=max>sum?max:sum;

       if(sum<0){
           sum=0;
         }

   }
   Collections.sort(arr);
   int sumo=0;
   for(int i=0;i<arr.size();i++){
       if(arr.get(i)>0){
           sumo+=arr.get(i);
       }
   }
       List<Integer> li=new ArrayList<>();
       li.add(max);
       if(arr.get(arr.size()-1)<0){
       li.add(arr.get(arr.size()-1));
       }
       else{
           li.add(sumo);
       }
       return li;
}

  • dehaka
     + 0 comments

    O(n)

    void maxSubarray(int n, const vector<int>& arr) {
    vector<int> subarray(n), subsequence(n);
    subarray[0] = arr[0];
    subsequence[0] = arr[0];
    for (int i=1; i < n; ++i) {
        subarray[i] = max(subarray[i-1] + arr[i], arr[i]);
        subsequence[i] = max( {subsequence[i-1], subsequence[i-1] + arr[i], arr[i]} );
    }
    cout << *max_element(subarray.begin(), subarray.end()) << ' ' << subsequence[n-1] << '\n';
}

  • vinay03015
     + 0 comments

    java 8 beginner way

    int sum=0;

       int max=arr.get(0);
   for(int i=0;i<arr.size();i++){
       sum+=arr.get(i);
       max=max>sum?max:sum;

       if(sum<0){
           sum=0;
         }

   }
   Collections.sort(arr);
   int sumo=0;
   for(int i=0;i<arr.size();i++){
       if(arr.get(i)>0){
           sumo+=arr.get(i);
       }
   }
       List<Integer> li=new ArrayList<>();
       li.add(max);
       if(arr.get(arr.size()-1)<0){
       li.add(arr.get(arr.size()-1));
       }
       else{
           li.add(sumo);
       }
       return li;
}

    }

  • nvhuu99
     + 0 comments

    I'm going to exlain my approach for the "find max sub array" part of this problem.:

    Let's say you have a sub-array, initially it's empty. For any item in the original array, you basically have 2 choices: 1. Add this item to the current sub-array. 2. Make a new sub-array starting from this item.

    With dynamic programming, you can keep tracking the max-sum of the sub-array for both of the choices you've made at each item in the original array.

    PHP code for this approach:

    function maxSubarray($arr)
{
    $dp = [];
    $maxArr = PHP_INT_MIN;
    foreach ($arr as $i => $v) {
        //Track the sum if we make a new sub-array with $v
				$dp[$i][0] = $v;
				
				// Track the sum if we append the sub-array with $v
        $dp[$i][1] = max($dp[$i - 1] ?? [0]) + $v;
				
        $maxArr = max($maxArr, ...$dp[$i]);
    }

    return $maxArr;
}