Skip to content

Instantly share code, notes, and snippets.

@secondfry
Last active August 11, 2021 10:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save secondfry/63541ba36f81c8c4d4167509dc39fd9d to your computer and use it in GitHub Desktop.
Save secondfry/63541ba36f81c8c4d4167509dc39fd9d to your computer and use it in GitHub Desktop.
7.md answer
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})
}
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")
}
module secondfry.ru/ozon
go 1.16
require github.com/stretchr/testify v1.7.0 // indirect
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=
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment