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

|

493 Discussions

|

  • arafat1419
     + 0 comments

    Java code

    public static List maxSubarray(List arr) { if (arr.size() == 1) { return List.of(arr.get(0), arr.get(0)); }

        if (arr.stream().allMatch(i -> i < 0)) {
        int maxNegative = arr.stream().mapToInt(Integer::intValue).max().orElse(Integer.MIN_VALUE);
        return List.of(maxNegative, maxNegative);
    }

    int currentValue = 0;
    int maxValue = 0;

    for (int i = 0; i < arr.size(); i++) {
        int value = arr.get(i);
        if (value >= 0) {
            currentValue += value;
        } else {
            if (currentValue + value > 0) {
                currentValue += value;
            } else {
                currentValue = Math.max(currentValue, value);
                currentValue = 0;
            }
        }

        maxValue = Math.max(maxValue, currentValue);
    }

    return List.of(maxValue, arr.stream()
            .filter(value -> value > 0)
            .mapToInt(Integer::intValue)
            .sum());
}

  • 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;
}

    }