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. Search
  4. Maximum Subarray Sum
  5. Discussions

Maximum Subarray Sum

Sort by

recency

|

344 Discussions

|

  • rajivaiyer
     + 0 comments

    My Java 8 solution, passing all test-cases, for Max Score of 60

    The idea is to do a "continuous trailing prefix modulo sum" as we iterate through the array, while comparing that with the maxModSum that we have seen so far & updating that as required. We maintain a prefixSumTreeSet to keep track of all the distinct prefixSums we have seen so far. We check if we have encountered a prefixSum that's higher than the curPrefixSum, and if so: then we use the higherPrefixTS value to update maxModSum as required.

    By using this approach, we only need to loop through the array once from start to finish (costing O(n) time). In each iteration, we spend some time going through the prefixSumTreeSet to locate the "higher" element, or to add a new element to the TreeSet (costing O(log(n)) time. This results in an overall Time Complexity of O(n * log(n)).

        public static long maximumSum(List<Long> a, long m) {
        // Write your code here
        long maxModSum = 0;
        long curPrefixSum = 0;

        TreeSet<Long> prefixSumTreeSet = new TreeSet<>();
        prefixSumTreeSet.add(0L);

        for (int aIdx = 0 ; aIdx < a.size() ; aIdx++) {

            curPrefixSum = ((curPrefixSum + a.get(aIdx) % m + m) % m);

            maxModSum = Math.max(maxModSum, curPrefixSum);

            Long higherPrefixTS = prefixSumTreeSet.higher(curPrefixSum);

            // System.err.println("aIdx=" + aIdx + " | a[" + aIdx + "]=" + a.get(aIdx) + 
            //                    " | curPrefixSum=" + curPrefixSum + " | maxModSum=" + 
            //                    maxModSum + " | higherPrefixTS=" + higherPrefixTS + 
            //                    " | prefixSumTreeSet=" + prefixSumTreeSet);

            if (higherPrefixTS != null) {
                maxModSum = Math.max(maxModSum, 
                                     ((curPrefixSum - higherPrefixTS + m) % m));
            }

            prefixSumTreeSet.add(curPrefixSum);

            // System.err.println("aIdx=" + aIdx + " | maxModSum=" + maxModSum + 
            //                    " | prefixSumTreeSet=" + prefixSumTreeSet);
        }

        return maxModSum;
    }

  • quote_unquote
     + 0 comments
    #
# Complete the 'maximumSum' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts following parameters:
#  1. LONG_INTEGER_ARRAY a
#  2. LONG_INTEGER m
#

import typing

class A(typing.NamedTuple):
    i: int
    v: int

def maximumSum(a, m):
    psum = 0
    x = []
    for i, v in enumerate(a):
        psum = (psum + v) % m
        x.append(A(i, psum))
    
    x = sorted(x, key=lambda e: e.v)
    # print(x)
    
    mx = x[-1].v
    for (i1, v1), (i2, v2) in zip(x[:-1], x[1:]):
        if (i1 > i2):
            mx = max(mx, v1 - v2 + m)

    return mx

  • patrickgao2020
     + 0 comments

    Here is my Python solution!

    def maximumSum(a, m):
    prefixes = [(0, -1)]
    for i in range(len(a)):
        prefixes.append(((prefixes[-1][0] + a[i]) % m, i))
    prefixes.sort()
    maximum = prefixes[-1][0]
    for (a, i1), (b, i2) in zip(prefixes[:-1], prefixes[1:]):
        if b > a and i1 > i2:
            maximum = max(maximum, (a - b) % m)
    return maximum

  • ArpitJai
     + 0 comments

    No need to use tree or sorted set. Just store all the prefix sums and sort. This idea comes from a different problem of minimising loss on house purchasing.

    def maximumSum(a, m):
    n = len(a)
    prefix_sums = [(a[0]%m,0)]
    for i in range(1,n):
        new_sum = a[i] + prefix_sums[i-1][0]
        prefix_sums.append((new_sum%m,i))
    prefix_sums.sort()
    max_sum = prefix_sums[-1][0]
    prev_index = prefix_sums[0][1]
    for i in range(1,n):
        if prefix_sums[i][0] == prefix_sums[i-1][0]:
            prev_index = max(prev_index, prefix_sums[i][1])
        else:
            if prefix_sums[i][1] < prev_index:
                max_sum = max(max_sum, prefix_sums[i-1][0] - prefix_sums[i][0] + m)
            prev_index = prefix_sums[i][1]
                
    return max_sum  

    q = int(input().

  • saravananduraiv1
     + 0 comments

    pure java... package geeksforgeeks; import java.util.*;

    public class Maxnumber {

    public static void main(String[] args) {
    int module, sum = 0, maxNumber = 0, start = 0, repeat = 2, sumofarray = 0, decrese = 1;
    Scanner sc = new Scanner(System.in);

    System.out.println("size");
    int n = sc.nextInt();
    int arr[] = new int[n];

    System.out.println("element");
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }

    System.out.println("modulo");
    module = sc.nextInt();

    // Sum of the whole array
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }

    int remainder = sum % module;
    maxNumber = Math.max(remainder, maxNumber);

    // Check subarrays with different lengths
    while (start != arr.length - 1) {
        int x = 0;
        int index = start;  // Start index for each iteration

        while (x != repeat && index < arr.length) {  // Prevent out of bounds
            for (int j = 0; j < decrese && index < arr.length; j++) {
                sumofarray += arr[index];
                index++;
            }
            remainder = (sum - sumofarray) % module;
            maxNumber = Math.max(remainder, maxNumber);
            sumofarray = 0;  // Reset sum for the next subarray
            x++;
        }
        start++;
        repeat++;
        decrese++;
    }

    System.out.println(maxNumber);

            (using array in java)...................



            sc.close();
}

    }