Maximum Subarray Sum

                            Solution in C :

In  C ++ :





#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

long long mod;
long long arr[100005];

set<long long> f;

int main() {
  
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d%lld", &n, &mod);
        for (int i = 0; i < n; ++i) {
            scanf("%lld", &arr[i]);
            arr[i] %= mod;
            if (i) arr[i] = (arr[i] + arr[i - 1]) % mod;
        }
        f.clear();
        f.insert(0);
        set<long long>::iterator it;
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            it = f.begin();
            if (it != f.end())
                ans = max(ans, arr[i] - *it);
            it = f.upper_bound(arr[i]);
            if (it != f.end())
                ans = max(ans, (arr[i] - *it + mod) % mod);
            f.insert(arr[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}









In  Java :





import java.util.*;


public class MaximizeSum {
  public static void main(String[] args) {
   Scanner in = new Scanner(System.in);
   int t = in.nextInt();
   while (t-- > 0) {
    int n = in.nextInt();
    long m = Long.parseLong(in.next());
    long[] arr = new long[n];
    for (int i = 0; i < n; i++) {
      long num = Long.parseLong(in.next()) % m;
     if (i == 0)
       arr[i] = num;
     else
       arr[i] = (arr[i -1] + num) % m; // get cumulative sum
    }
    TreeSet<Long> set = new TreeSet<Long>();
    long max = 0;
     for (long a : arr) {
       if (set.isEmpty()) {
        max = a;
        set.add(a);
       }
      else {
        max = Math.max(max, a);
        Long nextHighest = set.ceiling(a + 1);
        if (nextHighest != null)
          max = Math.max(max, a - nextHighest + m);
        set.add(a);
      }
     }
     System.out.println(max);
   }
  }
}









In   C :




#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef unsigned long long ll ;

#define max(x,y) (x ^ ((x ^ y) & -(x < y)))

ll *A,*A2,M;

int intcmp(const void *aa, const void *bb)
{
    const ll *a = aa, *b = bb;
    return (*a < *b) ? -1 : (*a > *b);
}


ll bisect_left(ll bisect_len,ll x ) {
  ll lo = 0;
  ll hi = bisect_len;
  ll mid = 0;
  while ( lo < hi ) {
    mid = (lo + hi) / 2;
    if ( A2[mid] < x ) lo = mid+1;
    else hi = mid;
  }

  if (lo != bisect_len && A2[lo] == x) {
    return x;
  }
  if (lo == 0) return A2[bisect_len-1];
  return A2[lo-1];
}


ll maxCrossingSum(ll l,ll m,ll h) {
  ll s0 = 0,maxls = 0,mm=0,r1,r2,bisect_len;
  ll i,j;
  for ( i = m -1,j=0 ; i >= l && i!= -1; i--,j++ ) {
    s0 = (s0 + A[i] ) % M;
    if ( maxls < s0 ) maxls = s0;
    A2[j] = s0;
  }
  bisect_len = j;
  if ( bisect_len == 0) {
    s0 = 0 ;maxls = 0;
    for ( i = m ; i <=h ;i++ ) {
      s0 = (s0 + A[i] ) % M;
      if ( maxls < s0 ) maxls = s0;
    }
    return maxls;
  }

  qsort(A2, j, sizeof(ll), intcmp);

  s0 = 0;
  for ( i = m ; i <= h ; i++) {
    s0 = (s0 + A[i] ) % M;
    r1 = ( s0 + bisect_left(bisect_len,M-s0-1)) % M;
    r2 = ( s0 + maxls ) % M;
    mm  = max(max(r1,r2),max(s0,mm));
  }
  return mm;
}
    


ll maxSum(ll l,ll h) {
  ll m,r1,r2,r3;
  if ( l == h ) return A[l] % M;
  m = ( l + h ) / 2;
  r1 = maxCrossingSum(l,m,h);
  r2 = maxSum(l,m);
  r3 = maxSum(m+1,h);
  
  return max(max(r1,r2),r3);
}

int main() {
  ll N,T,i,j,sum;

  scanf("%llu",&T);
  for (i = 0 ; i < T ; i++ ) {
      scanf("%llu",&N);
      scanf("%llu",&M);
      A = malloc(N * sizeof(ll));
      A2 = malloc(N * sizeof(ll));
      for ( j = 0 ; j < N ; j++) {
          scanf("%llu",&A[j]);
      }
      sum = maxSum(0,N-1);
      printf("%llu\n",sum);
      free(A);
      free(A2);
  }
  return 0;
}









In   Python3 :




import bisect

t = int(input())
for _ in range(t):
        n, m = map(int, input().split())
        a = list(map(int, input().split()))

        csum = [a[0] % m]
        for x in a[1:]:
                csum.append((csum[-1] + x) % m)

        seen = [0]
        mx = -1
        for s in csum:
                idx = bisect.bisect_left(seen, s)
                if idx < len(seen):
                        mx = max(mx, s, (s - seen[idx]) % m)
                else:
                        mx = max(mx, s)
                bisect.insort_left(seen, s)
                #print(seen)

        print(mx)