A few days ago, I was trying to resolve the classic maximum subarray conundrum in hackerrankand bumped into an interesting issue. When I submitted the solution, one testcase would fail. But if I ran the testcase individually, the result is right. After discussing in the IRC and Support, it seems the code didn’t pass some memory/time limit constraint in the environment, so I began to optimize my code.
My initial Go code is like this:
package main
import "fmt"
import "math"
import "os"
func MaxNonConArray(s []int) int {
var max int
if len(s) < 1 {
return 0
}
for _, v := range s {
if v > 0 {
max += v
}
}
if max == 0 {
max = s[0]
for _, v := range s[1:] {
if v > max {
max = v
}
}
}
return max
}
func MaxConArray(s []int) int {
var max int
if len(s) > 0 {
max = s[0]
currMax := s[0]
for _, v := range s[1:] {
currMax = int(math.Max(float64(currMax+v), float64(v)))
max = int(math.Max(float64(currMax), float64(max)))
}
}
return max
}
func main() {
//Enter your code here. Read input from STDIN. Print output to STDOUT
num := 0
s := [][]int(nil)
_, err := fmt.Scanf("%d", &num)
if err != nil {
os.Exit(1)
}
s = make([][]int, num)
for i := 0; i < len(s); i++ {
n := 0
_, err := fmt.Scanf("%d", &n)
if err != nil {
os.Exit(1)
}
s[i] = make([]int, n)
for j := 0; j < n; j++ {
_, err := fmt.Scanf("%d", &s[i][j])
if err != nil {
os.Exit(1)
}
}
}
for i := 0; i < len(s); i++ {
fmt.Println(MaxConArray(s[i]), MaxNonConArray(s[i]))
}
}
The main function would allocate a two-dimension slice to accommodate all the input elements. Suddenly I realized a one-dimension slice should be enough, and it could be reused after the wanted value was calculated. So the main code was changed like this:
func main() {
//Enter your code here. Read input from STDIN. Print output to STDOUT
var num int
_, err := fmt.Scanf("%d", &num)
if err != nil {
os.Exit(1)
}
for i := 0; i < num; i++ {
var n int
_, err := fmt.Scanf("%d", &n)
if err != nil {
os.Exit(1)
}
s := make([]int, n)
for j := 0; j < n; j++ {
_, err := fmt.Scanf("%d", &s[j])
if err != nil {
os.Exit(1)
}
}
fmt.Println(MaxConArray(s), MaxNonConArray(s))
}
}
Unfortunately, this time the testcase still can’t pass. So I resorted to C programming language:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int maxNonConSubArray(int *array, int n) {
int max = 0;
if (n > 0) {
for (int i = 0; i < n; i++) {
if (array[i] > 0) {
max += array[i];
}
}
if (max == 0) {
max = array[0];
for (int i = 1; i < n; i++) {
if (array[i] > max) {
max = array[i];
}
}
}
}
return max;
}
int MaxConSubArray(int *array, int n) {
int max = 0, currMax = 0;
if (n > 0) {
max = currMax = array[0];
for (int i = 1; i < n; i++) {
currMax = (currMax + array[i]) > array[i] ? (currMax + array[i]) : array[i];
max = max > currMax ? max : currMax;
}
}
return max;
}
int main() {
int num = 0;
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
if (scanf("%d", &num) != 1) {
return 1;
}
for (int i = 0; i < num; i++) {
int n = 0, *array = NULL;
if (scanf("%d", &n) != 1) {
return 1;
}
array = calloc(n, sizeof(int));
if (array == NULL) {
return 1;
}
for (int j = 0; j < n; j++) {
if (scanf("%d", array + j) != 1) {
return 1;
}
}
printf("%d %d\n",MaxConSubArray(array, n), maxNonConSubArray(array, n));
free(array);
}
return 0;
}
In the C code, I need to manage memory manually, and this time, the testcase didn’t complain, and the submission was success.