Four solutions of maximum sub segment and go

Maximum sub sum Go Four solutions of four

---

Preface

When the teacher assigned his homework, he encountered , Then although this problem is not very difficult , But such a problem with multiple solutions is worth recording , The code is directly on the back .

One 、 Code implementation ？

package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

var arr []int

func init() {
    
	// fmt.Println(" Maximum sub segment and calculation ")
	rand.Seed(time.Now().UnixNano())
		for i := 0; i < 10; i++ {
    
		item := rand.Intn(20) - 10
		arr = append(arr, item)
	}
}

//  Method 1 :  Divide and conquer  O(nlogn)
func method1() {
    
	//  Calculate the maximum 
	getMax := func(args... int) int {
    
		var maxData int = int(math.Inf(-1));
		for _, item := range args {
    
			if item > maxData {
    
				maxData = item
			}
		}
		return maxData
	}

	var maxsum func(l, r int) int

	maxsum = func(l, r int) int{
    
		if l == r {
    
			return arr[l]
		}
		mid := (l + r) / 2
		lsum := maxsum(l, mid)
		rsum := maxsum(mid + 1, r)
		sum1, sum2 := 0, 0
		lefts, rights := 0, 0
		for i := mid; i >= l; i-- {
    
			lefts += arr[i]
			if lefts > sum1 {
    
				sum1 = lefts
			}
		}

		for i := mid + 1; i <= r ; i++ {
    
			rights += arr[i]
			if rights > sum2 {
    
				sum2 = rights
			}
		}
		midsum := sum1 + sum2

		return getMax(lsum, rsum, midsum)
	}
	
	ans := maxsum(0, len(arr) - 1)
	if ans < 0 {
     ans = 0 }
	fmt.Println("maxData:", ans)
}


//  The most optimal 
//  Method 2 :  In data structure  o(n)
func method2() {
    
	var sum int = 0;
	var maxData int = 0;
	for _, item := range arr {
    
		sum += item
		if sum < 0 {
    
			sum = 0
		}
		if sum > maxData {
    
			maxData = sum
		}
	}
	fmt.Println("maxData:", maxData)
}

//  The brute force algorithm  O(n^2)
func method3() {
    
	n := len(arr)
	maxData := int(math.Inf(-1))
	sum := 0
	for i := 0; i < n; i++ {
    
		for j := i; j < n; j++ {
    
			sum += arr[j]
			if sum > maxData {
    
				maxData = sum
			}
		}
		sum = 0
	}
	fmt.Println("maxData: ", maxData)
}

//  Method four :  Dynamic programming  o(n)
func method4() {
    
	n := len(arr)
	ans := int(math.Inf(-1))
	dp := make([]int, n + 1)
	for i := 1; i <= n; i++ {
    
		if dp[i-1] + arr[i - 1] > arr[i - 1] {
    
			dp[i] = dp[i-1] + arr[i - 1]
		} else {
    
			dp[i] = arr[i - 1]
		}
		if dp[i] > ans {
    
			ans = dp[i]
		}
	}
	fmt.Println(" Maximum sub sum ",ans)
}

func main() {
    
	fmt.Println("data:",arr,"length:",len(arr))

	method1()
	method2()
	method3()
	method4()
}

---

summary

Tips ： Here is a summary of the article ：

Algorithm is still very important , You can practice more and record it