7.md answer

7.go

package main

import "fmt"

// Небольшой disclamier.
// Это решение создано так, как будто бы, я бы пошел на алгоритмическую секцию.
// Однако усложняющим фактором было то, что не было человека, с которым можно было бы обсудить решение.

// Теперь постфактум я посмотрел решение на Leetcode,
// узнал о https://en.wikipedia.org/wiki/Kadane%27s_algorithm
// и понимаю, что решение не самое оптимальное (плюс неверное в некоторых случаях).

type Interval struct {
	start, end, sum int
}

func printResult(input []int, output []int) []int {
	fmt.Println("input:", input)
	fmt.Println("output:", output)
	return output
}

func findSubarrayWithMaxSum(array []int) []int {
	if len(array) == 0 {
		return printResult(array, []int{0, 0})
	}

	var intervals []*Interval

	var current = &Interval{0, -1, array[0]}
	intervals = append(intervals, current)
	var idx = 0
	var max = array[0]

	for i := 1; i < len(array); i++ {
		var value = array[i]

		if value > max {
			idx = i
			max = value
		}

		if (current.sum < 0 && value < 0) || (current.sum >= 0 && value >= 0) {
			current.end = i
			current.sum += value
		} else {
			current.end = i - 1
			current = &Interval{i, -1, value}
			intervals = append(intervals, current)
		}
	}

	intervals[len(intervals)-1].end = len(array) - 1

	if array[0] < 0 {
		if len(intervals) == 1 {
			return printResult(array, []int{idx, idx})
		} else {
			intervals = append([]*Interval{{-1, -1, 0}}, intervals...)
		}
	}

	idx = 0
	max = intervals[0].sum

	// var joined bool

	// for {
	// 	joined = false

	for i := 1; i+1 < len(intervals); i += 2 {
		var prev = intervals[i-1]
		var cur = intervals[i]
		var next = intervals[i+1]

		if next.sum > max || (next.sum == max && intervals[idx].start == -1) {
			idx = i + 1
			max = next.sum
		}

		if cur.sum*-1 > prev.sum || cur.sum*-1 > next.sum {
			continue
		}

		// joined = true

		var sum = prev.sum + cur.sum + next.sum
		prev.sum = sum
		prev.end = next.end
		cur.start = prev.start
		cur.sum = sum
		cur.end = next.end
		next.start = prev.start
		next.sum = sum

		if prev.sum > max {
			idx = i - 1
			max = prev.sum
		}
	}

	// 	if !joined {
	// 		break
	// 	}
	// }

	return printResult(array, []int{intervals[idx].start, intervals[idx].end})
}

7_test.go

package main

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestExample(t *testing.T) {
	var input = []int{10, -3, -12, 8, 42, 1, -7, 0, 3}
	var output = []int{3, 5}
	assert.Equal(t, output, findSubarrayWithMaxSum(input), "they should be equal")
}

func TestBasic(t *testing.T) {
	var input = []int{1, 2, 3}
	var output = []int{0, 2}
	assert.Equal(t, output, findSubarrayWithMaxSum(input), "they should be equal")
}

func TestAllNegative(t *testing.T) {
	var input = []int{-1, -2, -3}
	var output = []int{0, 0}
	assert.Equal(t, output, findSubarrayWithMaxSum(input), "they should be equal")
}

// В задании не указано, что делать в таком случае.
// В данной реализации возвращается первый отрезок.
func TestAllSameNegative(t *testing.T) {
	var input = []int{-1, -1, -1}
	var output = []int{0, 0}
	assert.Equal(t, output, findSubarrayWithMaxSum(input), "they should be equal")
}

// В задании не указано, что делать в таком случае.
// В данной реализации возвращается отрезок максимальной длины.
func TestSameSum(t *testing.T) {
	var input = []int{1, -1, 1}
	var output = []int{0, 2}
	assert.Equal(t, output, findSubarrayWithMaxSum(input), "they should be equal")
}

// В задании не указано, что делать в таком случае.
// В данной реализации возвращается 0, 0
func TestEmpty(t *testing.T) {
	var input = []int{}
	var output = []int{0, 0}
	assert.Equal(t, output, findSubarrayWithMaxSum(input), "they should be equal")
}

func TestMoreTests(t *testing.T) {
	assert.Equal(t, []int{1, 6}, findSubarrayWithMaxSum([]int{-5, 9, 5, 4, -2, 0, 4}), "they should be equal")
	assert.Equal(t, []int{1, 3}, findSubarrayWithMaxSum([]int{-5, 9, 5, 4, -7, 0, 4}), "they should be equal")
	assert.Equal(t, []int{1, 3}, findSubarrayWithMaxSum([]int{-1, 0, 0, 0, -1, 0}), "they should be equal")
	assert.Equal(t, []int{0, 0}, findSubarrayWithMaxSum([]int{-1}), "they should be equal")
	assert.Equal(t, []int{0, 0}, findSubarrayWithMaxSum([]int{0, -1}), "they should be equal")
	assert.Equal(t, []int{1, 1}, findSubarrayWithMaxSum([]int{-1, 0}), "they should be equal")
	assert.Equal(t, []int{2, 2}, findSubarrayWithMaxSum([]int{-1, -1, 0}), "they should be equal")
	assert.Equal(t, []int{2, 5}, findSubarrayWithMaxSum([]int{-1, -1, 0, 0, 0, 0}), "they should be equal")
}

// см. disclamier в файле 7.go
// Этот тесткейс подсвечивает две проблемы:
// 1. Мой алгоритм склейки нужно запускать log N раз, чтобы убедиться, что склеек больше не случается.
// 2. Даже если склейки больше не приведут к лучшему результату, выводится не самый длинный отрезок.
//
// Если бы я нашел этот тесткейс раньше, я бы еще подумал о решении за линейное время.
func TestComplicated(t *testing.T) {
	assert.Equal(t, []int{0, 4}, findSubarrayWithMaxSum([]int{10, -8, 6, -4, 8}), "they should be equal")
}

go.mod

module secondfry.ru/ozon

go 1.16

require github.com/stretchr/testify v1.7.0 // indirect

go.sum

github.com/davecgh/go-spew v1.1.0 h1:ZDRjVQ15GmhC3fiQ8ni8+OwkZQO4DARzQgrnXU1Liz8=
github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
github.com/stretchr/objx v0.1.0 h1:4G4v2dO3VZwixGIRoQ5Lfboy6nUhCyYzaqnIAPPhYs4=
github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
github.com/stretchr/testify v1.7.0 h1:nwc3DEeHmmLAfoZucVR881uASk0Mfjw8xYJ99tb5CcY=
github.com/stretchr/testify v1.7.0/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c h1:dUUwHk2QECo/6vqA44rthZ8ie2QXMNeKRTHCNY2nXvo=
gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=