Be the first user to complete this post

  • 0
Add to List

Maximum Difference between SubArrays from an Array O(N^2)

Input : A[1….n]

Output : Max Difference between ∑A[i…j] and ∑A[k…l]

Complexity : O(n*n)

Example :

A[-1,3,-1,-1,5]

Max difference between SubArrays Sum from an Array will be

Sum of SubArray(max)-Sum of SubArray(min)

So in this case, Sum of SubArray(max) will contain [3,-1,-1,5] =  6

and Sum of SubArray(min) will contain [-1,-1] =  -2

So Max difference will be 6-(-2) = 8

Complete code:

 Sub SubArrayMax()
    Dim arrA(4)
    arrA(0) = -1
    arrA(1) = 3
    arrA(2) = -1
    arrA(3) = -1
    arrA(4) = 5

    intMax = arrA(0)
    intMin = arrA(0)
    intTemp = 0
    For i = 0 To UBound(arrA)
        intTemp = 0
        For j = i To UBound(arrA)
            intTemp = arrA(j) + intTemp
            If intMax < intTemp Then
                intMax = intTemp
            End If
            If intMin > intTemp Then
                intMin = intTemp
            End If
        Next
    Next
        MsgBox "Max SubArray(Sum) Value : " & intMax & vbCrLf & "Min SubArray(Sum) Value : " & intMin & vbCrLf & "Max Difference bw SubArrays is " & (intMax - intMin)
End Sub
SubArray Max and Min
SubArray Max and Min

Happy Macro­ing :)

Sumit Jain