You are given an array A consisting of the integers −1, 0 and 1. A slice of that array is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. Your task is to find the longest slice of A whose elements yield a non-negative sum.
Write a function:
class Solution { public int solution(int[] A); }
that, given an array A of length N, consisting only of the values −1, 0, 1, returns the length of the longest slice of A that yields a non-negative sum. If there's no such slice, your function should return 0.
For example, given A = [−1, −1, 1, −1, 1, 0, 1, −1, −1], your function should return 7, as the slice starting at the second position and ending at the eighth is the longest slice with a non-negative sum.
For another example, given A = [1, 1, −1, −1, −1, −1, −1, 1, 1] your function should return 4: both the first four elements and the last four elements of array A are longest valid slices.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [2..100,000];
- each element of array A is an integer within the range [−1..1].
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
using System;
// you can also use other imports, for example:
using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
using System;
using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
var ret = 0;
var totalSum = 0;
// <totalSum, MinPositiveIndex> pair
var minIndexes = new Dictionary<int, int>();
// stack with minus ones
var minusOnes = new Stack<int>();
// stack with plus ones
var plusOnes = new Stack<int>();
var precedingZerosStart = -1;
for (int i=0; i<A.Length; i++)
{
totalSum += A[i];
if(totalSum >= 0)
{
var maxAtIndex = i + 1;
ret = Math.Max(ret, maxAtIndex);
}
switch(A[i])
{
case 0:
if (precedingZerosStart == -1)
precedingZerosStart = i;
if(minIndexes.ContainsKey(totalSum) && minIndexes[totalSum] != -1)
{
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else if(precedingZerosStart != -1)
{
var maxAtIndex = i - precedingZerosStart + 1;
ret = Math.Max(ret, maxAtIndex);
}
break;
case 1:
if (precedingZerosStart != -1)
{
plusOnes.Push(precedingZerosStart);
}
else
{
plusOnes.Push(i);
}
if (totalSum < 0)
{
if(!minIndexes.ContainsKey(totalSum))
{
// first appearance of this negative total sum
minIndexes.Add(totalSum, -1);
}
else
{
if(minIndexes[totalSum] == -1)
{
var popMinusOne = minusOnes.Pop();
minIndexes[totalSum] = popMinusOne;
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else
{
if(minusOnes.Count > 0)
{
var popMinusOne = minusOnes.Pop();
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
}
}
}
else
{
if (minusOnes.Count > 0)
{
var popMinusOne = minusOnes.Pop();
}
}
precedingZerosStart = -1;
break;
case -1:
if (precedingZerosStart != -1)
{
minusOnes.Push(precedingZerosStart);
}
else
{
minusOnes.Push(i);
}
if (totalSum < 0)
{
if (!minIndexes.ContainsKey(totalSum))
{
// first appearance of this negative total sum
minIndexes.Add(totalSum, -1);
}
else
{
if (minIndexes[totalSum] == -1)
{
// set the real min index
var popPlusOne = plusOnes.Pop();
minIndexes[totalSum] = popPlusOne;
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else
{
if(plusOnes.Count > 0)
{
var popMinusOne = plusOnes.Pop();
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
}
}
}
else
{
if (plusOnes.Count > 0)
{
var popPlusOne = plusOnes.Pop();
}
}
precedingZerosStart = -1;
break;
}
}
foreach (var d in minIndexes)
{
Console.WriteLine($"Total Sum: {d.Key}, Min Index: {d.Value}");
}
Console.WriteLine($"MAX ARRAY LENGTH: {ret}");
return ret;
}
}
using System;
using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
var ret = 0;
var totalSum = 0;
// <totalSum, MinPositiveIndex> pair
var minIndexes = new Dictionary<int, int>();
// stack with minus ones
var minusOnes = new Stack<int>();
// stack with plus ones
var plusOnes = new Stack<int>();
var precedingZerosStart = -1;
for (int i=0; i<A.Length; i++)
{
totalSum += A[i];
if(totalSum >= 0)
{
var maxAtIndex = i + 1;
ret = Math.Max(ret, maxAtIndex);
}
switch(A[i])
{
case 0:
if (precedingZerosStart == -1)
precedingZerosStart = i;
if(minIndexes.ContainsKey(totalSum) && minIndexes[totalSum] != -1)
{
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else if(precedingZerosStart != -1)
{
var maxAtIndex = i - precedingZerosStart + 1;
ret = Math.Max(ret, maxAtIndex);
}
break;
case 1:
if (precedingZerosStart != -1)
{
plusOnes.Push(precedingZerosStart);
}
else
{
plusOnes.Push(i);
}
if (totalSum < 0)
{
if(!minIndexes.ContainsKey(totalSum))
{
// first appearance of this negative total sum
minIndexes.Add(totalSum, -1);
}
else
{
if(minIndexes[totalSum] == -1)
{
var popMinusOne = minusOnes.Pop();
minIndexes[totalSum] = popMinusOne;
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else
{
if(minusOnes.Count > 0)
{
var popMinusOne = minusOnes.Pop();
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
}
}
}
else
{
if (minusOnes.Count > 0)
{
var popMinusOne = minusOnes.Pop();
}
}
precedingZerosStart = -1;
break;
case -1:
if (precedingZerosStart != -1)
{
minusOnes.Push(precedingZerosStart);
}
else
{
minusOnes.Push(i);
}
if (totalSum < 0)
{
if (!minIndexes.ContainsKey(totalSum))
{
// first appearance of this negative total sum
minIndexes.Add(totalSum, -1);
}
else
{
if (minIndexes[totalSum] == -1)
{
// set the real min index
var popPlusOne = plusOnes.Pop();
minIndexes[totalSum] = popPlusOne;
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else
{
if(plusOnes.Count > 0)
{
var popMinusOne = plusOnes.Pop();
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
}
}
}
else
{
if (plusOnes.Count > 0)
{
var popPlusOne = plusOnes.Pop();
}
}
precedingZerosStart = -1;
break;
}
}
return ret;
}
}
using System;
using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
var ret = 0;
var totalSum = 0;
// <totalSum, MinPositiveIndex> pair
var minIndexes = new Dictionary<int, int>();
// stack with minus ones
var minusOnes = new Stack<int>();
// stack with plus ones
var plusOnes = new Stack<int>();
var precedingZerosStart = -1;
for (int i=0; i<A.Length; i++)
{
totalSum += A[i];
if(totalSum >= 0)
{
var maxAtIndex = i + 1;
ret = Math.Max(ret, maxAtIndex);
}
switch(A[i])
{
case 0:
if (precedingZerosStart == -1)
precedingZerosStart = i;
if(minIndexes.ContainsKey(totalSum) && minIndexes[totalSum] != -1)
{
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else if(precedingZerosStart != -1)
{
var maxAtIndex = i - precedingZerosStart + 1;
ret = Math.Max(ret, maxAtIndex);
}
break;
case 1:
if (precedingZerosStart != -1)
{
plusOnes.Push(precedingZerosStart);
}
else
{
plusOnes.Push(i);
}
if (totalSum < 0)
{
if(!minIndexes.ContainsKey(totalSum))
{
// first appearance of this negative total sum
minIndexes.Add(totalSum, -1);
}
else
{
if(minIndexes[totalSum] == -1)
{
var popMinusOne = minusOnes.Pop();
minIndexes[totalSum] = popMinusOne;
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else
{
if(minusOnes.Count > 0)
{
var popMinusOne = minusOnes.Pop();
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
}
}
}
else
{
if (minusOnes.Count > 0)
{
var popMinusOne = minusOnes.Pop();
}
}
precedingZerosStart = -1;
break;
case -1:
if (precedingZerosStart != -1)
{
minusOnes.Push(precedingZerosStart);
}
else
{
minusOnes.Push(i);
}
if (totalSum < 0)
{
if (!minIndexes.ContainsKey(totalSum))
{
// first appearance of this negative total sum
minIndexes.Add(totalSum, -1);
}
else
{
if (minIndexes[totalSum] == -1)
{
// set the real min index
var popPlusOne = plusOnes.Pop();
minIndexes[totalSum] = popPlusOne;
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else
{
if(plusOnes.Count > 0)
{
var popMinusOne = plusOnes.Pop();
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
}
}
}
else
{
if (plusOnes.Count > 0)
{
var popPlusOne = plusOnes.Pop();
}
}
precedingZerosStart = -1;
break;
}
}
return ret;
}
}
using System;
using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
var ret = 0;
var totalSum = 0;
// <totalSum, MinPositiveIndex> pair
var minIndexes = new Dictionary<int, int>();
// stack with minus ones
var minusOnes = new Stack<int>();
// stack with plus ones
var plusOnes = new Stack<int>();
var precedingZerosStart = -1;
for (int i=0; i<A.Length; i++)
{
totalSum += A[i];
if(totalSum >= 0)
{
var maxAtIndex = i + 1;
ret = Math.Max(ret, maxAtIndex);
}
switch(A[i])
{
case 0:
if (precedingZerosStart == -1)
precedingZerosStart = i;
if(minIndexes.ContainsKey(totalSum) && minIndexes[totalSum] != -1)
{
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else if(precedingZerosStart != -1)
{
var maxAtIndex = i - precedingZerosStart + 1;
ret = Math.Max(ret, maxAtIndex);
}
break;
case 1:
if (precedingZerosStart != -1)
{
plusOnes.Push(precedingZerosStart);
}
else
{
plusOnes.Push(i);
}
if (totalSum < 0)
{
if(!minIndexes.ContainsKey(totalSum))
{
// first appearance of this negative total sum
minIndexes.Add(totalSum, -1);
}
else
{
if(minIndexes[totalSum] == -1)
{
var popMinusOne = minusOnes.Pop();
minIndexes[totalSum] = popMinusOne;
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else
{
if(minusOnes.Count > 0)
{
var popMinusOne = minusOnes.Pop();
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
}
}
}
else
{
if (minusOnes.Count > 0)
{
var popMinusOne = minusOnes.Pop();
}
}
precedingZerosStart = -1;
break;
case -1:
if (precedingZerosStart != -1)
{
minusOnes.Push(precedingZerosStart);
}
else
{
minusOnes.Push(i);
}
if (totalSum < 0)
{
if (!minIndexes.ContainsKey(totalSum))
{
// first appearance of this negative total sum
minIndexes.Add(totalSum, -1);
}
else
{
if (minIndexes[totalSum] == -1)
{
// set the real min index
var popPlusOne = plusOnes.Pop();
minIndexes[totalSum] = popPlusOne;
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
else
{
if(plusOnes.Count > 0)
{
var popMinusOne = plusOnes.Pop();
var maxAtIndex = i - minIndexes[totalSum] + 1;
ret = Math.Max(ret, maxAtIndex);
}
}
}
}
else
{
if (plusOnes.Count > 0)
{
var popPlusOne = plusOnes.Pop();
}
}
precedingZerosStart = -1;
break;
}
}
return ret;
}
}
The solution obtained perfect score.