class RangeChunk
attr_accessor :r_start, :r_end, :r_sum
def initialize
( nStart
)
@r_start = nStart
@r_end =
0
@r_sum =
0
end
end
class StrangeRange
def initialize
( _rangeSize =
0 )
@totalRange = Array.
new( _rangeSize
)
nCount =
0
@totalRange.
each do | element |
# -500 ~ 500
element =
500 -
rand(1000)
@totalRange[nCount
] = element
print nCount.to_s +
". " + element.to_s +
"\n"
nCount +=
1
end
end
def selectBigRange
nCurrnetIndex =
0
nCurrnetBigRangeChunk =
0
nCurrentBigSumOfChunk =
0
bPlusRange = true
aChunkArray = Array.
new
aRangeChunk = RangeChunk.
new(0)
@totalRange.
each do | element |
if bPlusRange
if element >=
0
aRangeChunk.r_end = nCurrnetIndex
aRangeChunk.r_sum += element
else
bPlusRange = false
# 처음을 양수구간이라고 가정했는데, 알고 보니 음수구간이었다면 그냥 음수구간으로 변경시켜주기
if aRangeChunk.r_end == nCurrnetIndex
aRangeChunk.r_sum = element
nCurrentBigSumOfChunk = element
else
aRangeChunk.r_end = nCurrnetIndex -
1
aChunkArray.
push( aRangeChunk
)
if aRangeChunk.r_sum > nCurrentBigSumOfChunk
nCurrentBigSumOfChunk = aRangeChunk.r_sum
nCurrnetBigRangeChunk = aChunkArray.
length -
1
end
aRangeChunk = RangeChunk.
new( nCurrnetIndex
)
aRangeChunk.r_sum += element
end
end
else
if element >=
0
bPlusRange = true
aRangeChunk.r_end = nCurrnetIndex -
1
aChunkArray.
push( aRangeChunk
)
aRangeChunk = RangeChunk.
new( nCurrnetIndex
)
aRangeChunk.r_sum += element
else
aRangeChunk.r_end = nCurrnetIndex
aRangeChunk.r_sum += element
end
end
nCurrnetIndex +=
1
end
#마지막 구간
aRangeChunk.r_end = nCurrnetIndex -
1
aChunkArray.
push( aRangeChunk
)
# 음수/양수구간으로 나눈게 맞는지 확인하기.
aChunkArray.
each do | chunk_element |
print chunk_element.r_sum.to_s +
"\n"
end
aBeforChunk = nil
aAfterChunk = nil
nNewBigSumOfChunk = nCurrentBigSumOfChunk
(nCurrnetBigRangeChunk
-1).step
(0,
-1) do | i |
nNewBigSumOfChunk += aChunkArray
[i
].r_sum
if nNewBigSumOfChunk > nCurrentBigSumOfChunk
nCurrentBigSumOfChunk = nNewBigSumOfChunk
aBeforChunk = aChunkArray
[i
]
end
end
nNewBigSumOfChunk = nCurrentBigSumOfChunk
(nCurrnetBigRangeChunk
+1).step
(aChunkArray.length
-1,
1) do | i |
nNewBigSumOfChunk += aChunkArray
[i
].r_sum
if nNewBigSumOfChunk > nCurrentBigSumOfChunk
nCurrentBigSumOfChunk = nNewBigSumOfChunk
aAfterChunk = aChunkArray
[i
]
end
end
nResultStartRange = aBeforChunk == nil ? aChunkArray
[nCurrnetBigRangeChunk
].r_start : aBeforChunk.r_start
nResultEndtRange = aAfterChunk == nil ? aChunkArray
[nCurrnetBigRangeChunk
].r_end : aAfterChunk.r_end
print "Big Range Start : " + nResultStartRange.to_s +
", End : " + nResultEndtRange.to_s +
". and Sum : " + nCurrentBigSumOfChunk.to_s +
"\n"
end
end
if __FILE__ == $
0
nRangeCount = ARGV.empty? ?
10 : ARGV
[0].to_i
aSample = StrangeRange.
new( nRangeCount
)
aSample.selectBigRange
end