Go solution to LeetCode 1005 Maximize Sum Of Array After K Negations

In this Leetcode problem, we need to optimize the sum for all the elements in an array A by successively flipping elements A[i] into -A[i]. We can do this K times and we need to return the sum of all elements when we do it optimally.

Problem statement

Naive solution, recurse on K

To construct a very naive solution we can implement a greedy recursion. That is find the minimum element of the array, flip it, and then recusrively call with K-1, I tried it, the solution was accepted:

func largestSumAfterKNegations(A []int, K int) int {
    if K == 0 {
        return sum(A)
    } else {
        minIndex := minIndex(A)
        A[minIndex] = - A[minIndex]
        return largestSumAfterKNegations(A, K - 1)
    }
}
func sum(A []int) int {
    sum := 0
    for _, v := range A {
        sum += v
    }
    return sum
}
func minIndex(A []int) int {
    min := 101
    minIndex := -1
    for i,v := range A {
        if v < min {
            minIndex = i
            min = v
        }
    }
    return minIndex
}

The time complexity is O(len(A) * K) and the space complexity is O(K).

Construct a linear solution