Table of Contents
Maximum Subarray Sum – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Maximum Subarray Sum HackerRank Solution
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
int main() {
int T;
scanf("%d", &T);
rep(ii, T) {
int N; long long M;
scanf("%d%lld", &N, &M);
vector<long long> A(N);
rep(i, N)
scanf("%lld", &A[i]);
long long sum = 0, ans = 0;
set<long long> s;
rep(i, N) {
s.insert(sum);
(sum += A[i]) %= M;
//sum - sum_i
amax(ans, (sum - *s.begin() + M) % M);
amax(ans, (sum - *s.lower_bound(sum+1) + M) % M);
}
printf("%lld\n", ans);
}
return 0;
}
Java Maximum Subarray Sum HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.List;
public class B {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
for(int T = ni();T >= 1;T--){
int n = ni();
long m = nl();
long[] a = new long[n+1];
for(int i = 0;i < n;i++){
a[i+1] = (a[i] + nl()) % m;
}
long[][] as = new long[n+1][];
for(int i = 0;i < n+1;i++){
as[i] = new long[]{a[i], i};
}
Arrays.sort(as, new Comparator<long[]>() {
public int compare(long[] a, long[] b) {
return Long.compare(a[0], b[0]);
}
});
long[] asv = new long[n+1];
int[] ias = new int[n+1];
for(int i = 0;i < n+1;i++){
ias[(int)as[i][1]] = i;
asv[i] = as[i][0]*2;
}
LST lst = new LST(n+2);
long max = 0;
for(int i = 0;i < n+1;i++){
if(i > 0){
int wh = Arrays.binarySearch(asv, a[i]*2+1);
wh = -wh-1;
int nex = lst.next(wh);
if(nex == -1){
nex = lst.next(0);
}
max = Math.max(max, (a[i]-as[nex][0]+m)%m);
}
lst.set(ias[i]);
}
out.println(max);
}
}
public static class LST {
public long[][] set;
public int n;
// public int size;
public LST(int n) {
this.n = n;
int d = 1;
for(int m = n;m > 1;m>>>=6, d++);
set = new long[d][];
for(int i = 0, m = n>>>6;i < d;i++, m>>>=6){
set[i] = new long[m+1];
}
// size = 0;
}
// FIXME
public LST set(int l, int r)
{
if(0 <= l && l <= r && r <= n){
setRange(r);
unsetRange(l-1);
}
return this;
}
public LST setRange(int r)
{
for(int i = 0;i < set.length;i++, r>>>=6){
for(int j = 0;j < r>>>6;j++){
set[i][j] = -1;
}
set[i][r>>>6] |= (1L<<r+1)-1;
}
return this;
}
public LST unsetRange(int r)
{
if(r >= 0){
for(int i = 0;i < set.length;i++, r>>>=6){
for(int j = 0;j < r>>>6;j++){
set[i][j] = 0;
}
set[i][r>>>6] &= ~((1L<<r+1)-1);
}
}
return this;
}
public LST set(int pos)
{
if(pos >= 0 && pos < n){
// if(!get(pos))size++;
for(int i = 0;i < set.length;i++, pos>>>=6){
set[i][pos>>>6] |= 1L<<pos;
}
}
return this;
}
public LST unset(int pos)
{
if(pos >= 0 && pos < n){
// if(get(pos))size--;
for(int i = 0;i < set.length && (i == 0 || set[i-1][pos] == 0L);i++, pos>>>=6){
set[i][pos>>>6] &= ~(1L<<pos);
}
}
return this;
}
public boolean get(int pos)
{
return pos >= 0 && pos < n && set[0][pos>>>6]<<~pos<0;
}
public int prev(int pos)
{
for(int i = 0;i < set.length && pos >= 0;i++, pos>>>=6, pos--){
int pre = prev(set[i][pos>>>6], pos&63);
if(pre != -1){
pos = pos>>>6<<6|pre;
while(i > 0)pos = pos<<6|63-Long.numberOfLeadingZeros(set[--i][pos]);
return pos;
}
}
return -1;
}
public int next(int pos)
{
for(int i = 0;i < set.length && pos>>>6 < set[i].length;i++, pos>>>=6, pos++){
int nex = next(set[i][pos>>>6], pos&63);
if(nex != -1){
pos = pos>>>6<<6|nex;
while(i > 0)pos = pos<<6|Long.numberOfTrailingZeros(set[--i][pos]);
return pos;
}
}
return -1;
}
private static int prev(long set, int n)
{
long h = Long.highestOneBit(set<<~n);
if(h == 0L)return -1;
return Long.numberOfTrailingZeros(h)-(63-n);
}
private static int next(long set, int n)
{
long h = Long.lowestOneBit(set>>>n);
if(h == 0L)return -1;
return Long.numberOfTrailingZeros(h)+n;
}
@Override
public String toString()
{
List<Integer> list = new ArrayList<Integer>();
for(int pos = next(0);pos != -1;pos = next(pos+1)){
list.add(pos);
}
return list.toString();
}
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Maximum Subarray Sum HackerRank Solution
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)
Python 2 Maximum Subarray Sum HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
import bisect
def max_mod(array, M):
L = [0] * (len(array) + 1)
for i in range(1, len(L)):
L[i] = L[i - 1] + array[i - 1]
acc = 0
done = []
# print L
for i in range(len(L)):
x = L[i] % M
j = bisect.bisect_right(done, x)
acc = max(acc, x)
# print done, (x, j), acc
if j < i:
acc = max(acc, (L[i] - done[j]) % M)
done.insert(j, x)
return acc
for _ in range(input()):
N, M = map(int, raw_input().split(" "))
array = map(int, raw_input().split(" "))
print max_mod(array, M)
C Maximum Subarray Sum HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
unsigned long max_sum(
unsigned long *partial_sums,
unsigned long *dest,
unsigned length,
unsigned long target
) {
if (length < 2)
return (*dest = *partial_sums);
unsigned
lower_len = length >> 1,
upper_len = length - lower_len;
unsigned long
lower[lower_len],
upper[upper_len],
max_left = max_sum(partial_sums, lower, lower_len, target),
max_right = max_sum(&partial_sums[lower_len], upper, upper_len, target),
max = max_left > max_right ? max_left : max_right;
unsigned lesser = 0, greater = 0;
while (lesser < lower_len && greater < upper_len)
if (upper[greater] < lower[lesser]) {
*dest = upper[greater++];
unsigned long other_max = (*dest++ - lower[lesser]) + target;
if (other_max > max)
max = other_max;
} else
*dest++ = lower[lesser++];
memcpy(dest, &lower[lesser], (lower_len - lesser) * sizeof(*dest));
memcpy(&dest[lower_len - lesser], &upper[greater], (upper_len - greater) * sizeof(*dest));
return max;
}
int main() {
unsigned length;
unsigned long test_case, limit, index;
static unsigned long
items[100000],
buffer[100001] = {[0] = 0},
*partial_sums = &buffer[1];
for (scanf("%lu", &test_case); test_case--; ) {
scanf("%u", &length);
scanf("%lu", &limit);
for (index = 0; index < length; index++) {
scanf("%lu", &items[index]);
items[index] %= limit;
partial_sums[index] = (items[index] + partial_sums[index - 1ULL]) % limit;
}
static unsigned long ordered[100000];
unsigned long max = max_sum(partial_sums, ordered, length, limit);
printf("%lu\n", max);
}
return 0;
}
Leave a comment below
