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

|

494 Discussions

|

  • nandini_97
     + 0 comments

    `Java: Simple Code for Beginner:

    public static List maxSubarray(List arr) {

    int maxContiguous = Integer.MIN_VALUE;
int currSum = 0;

 int maxNonContiguous = Integer.MIN_VALUE;
 int nonContiguousSum = 0;
 boolean hasPositive = false;

 for (int num : arr) {

     // Contiguous (Kadane’s algo): subarray
     currSum = Math.max(num, currSum + num);
     maxContiguous = Math.max(maxContiguous, currSum);

     // Non-contiguous: subsequence
     if (num > 0) {

         nonContiguousSum += num;
         hasPositive = true;
     }

     maxNonContiguous = Math.max(maxNonContiguous, num); // track max Element when all are negatives in list
 }

 if (!hasPositive) {

     nonContiguousSum = maxNonContiguous; // in case all are negative
 }

 List<Integer> result = new ArrayList<>();
 result.add(maxContiguous);
 result.add(nonContiguousSum);
 return result;

    } `

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