Maximum Subarray Sum

Sort by

recency

|

343 Discussions

|

  • + 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
    
  • + 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
    
  • + 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().
    
  • + 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();
    }
    

    }

  • + 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);
        sc.close();
    }
    

    }