# encoding: ascii # api: powershell # title: Sub-Array with the Large # description: http://www.mytechinterviews.com/sub-array-with-the-largest-sum # version: 0.1 # type: function # author: BobLobLaw # license: CC0 # function: New-RandomArray # x-poshcode-id: 4177 # x-archived: 2014-11-13T07:00:20 # x-published: 2014-05-21T08:21:00 # # Question: You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum. # On Sunday Netflix will release 15 new episodes of Arrested Development! YEAH! # function New-RandomArray{ #.SYNOPSIS #Generates a random number array. #.DESCRIPTION #Each element of the array is a random number between the Maximum and Minimum #values. [cmdletbinding()] Param( #The amount of random number you want in your array. [Alias('ArrayLength','Count','Size')] [int]$Length=300, #Max value for each random number in the array. [int]$Maximum=1000, #Min value for each random number in the array. [int]$Minimum=-1000 ) Write-Verbose 'Generating random array ...' return (1..$Length | ForEach-Object {Get-Random -Maximum $Maximum -Minimum $Minimum}) } function Get-MaxSumSubArray{ #.SYNOPSIS #You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum. #.DESCRIPTION #That's what it does. [cmdletbinding()] Param( #The array you want to use. If you don't have one I'll MAKE one! [int[]]$Array=(New-RandomArray -Verbose), #The length of the sub array. [int]$SubArrayLength=10 ) if($SubArrayLength -ge $Array.Count){ throw "You are not finding a sub-array." } $BeginningIndexOfLastSubArray = $Array.Count - $SubArrayLength <# One line command 0..$BeginningIndexOfLastSubArray | ForEach-Object {$array[$_..($_+$SubArrayLength-1)] | Measure-Object -Sum} | Sort-Object -Property Sum -Descending | Select-Object -First 1 #> $MaxSumSubArray = [PSCustomObject]@{Sum=[int]::MinValue;StartIndex=$null;EndIndex=$null} #Could make faster with jobs. for($i=0;$i-le$BeginningIndexOfLastSubArray;$i++){ Write-Verbose "Calculating sub-array {$($array[$i..($i+$SubArrayLength-1)] -join ', ')}." $tmpsum = $array[$i..($i+$SubArrayLength-1)] | Measure-Object -Sum if($tmpsum.Sum -gt $MaxSumSubArray.Sum){ $MaxSumSubArray.Sum = $tmpsum.Sum $MaxSumSubArray.StartIndex = $i $MaxSumSubArray.EndIndex = $i+$SubArrayLength-1 } } return $MaxSumSubArray } Get-MaxSumSubArray -Verbose