配列とマトリクスの問題---サブ配列の最大累積と問題
1211 ワード
【テーマ】
1つの配列arrが与えられ、サブ配列の最大累積和、例えばarr=[1,−2,3,5,−2,6,1]が返され、すべてのサブ配列において[3,5,−2,6]が最大累積和を12とすることができるので、12が返される.
【基本的な考え方】
1つの変数curSumを用いて各ステップの累積和を記録し,正数curSum増加に遍歴し,負減少に遍歴した.curSum<0の場合、現在の位置に累積して0未満の結果が得られたことを示す場合、累積されたこの部分は、curSum=0となる最大累積およびサブ配列のプレフィックスとして使用できないに違いない.グローバル変数を使用して、発生した最大累積和を記録します.
以下、python 3を用いる.5実装されたコード.
1つの配列arrが与えられ、サブ配列の最大累積和、例えばarr=[1,−2,3,5,−2,6,1]が返され、すべてのサブ配列において[3,5,−2,6]が最大累積和を12とすることができるので、12が返される.
【基本的な考え方】
1つの変数curSumを用いて各ステップの累積和を記録し,正数curSum増加に遍歴し,負減少に遍歴した.curSum<0の場合、現在の位置に累積して0未満の結果が得られたことを示す場合、累積されたこの部分は、curSum=0となる最大累積およびサブ配列のプレフィックスとして使用できないに違いない.グローバル変数を使用して、発生した最大累積和を記録します.
以下、python 3を用いる.5実装されたコード.
def maxSum(arr):
if arr == None or len(arr) == 0:
return
maxSum = -sys.maxsize
curSum = 0
for i in range(len(arr)):
curSum += arr[i]
maxSum = max(maxSum, curSum)
curSum = curSum if curSum > 0 else 0
return maxSum