最大连续子数组和算法(动态规划)

题目:


给出一个数组,求其最大连续子数组和  

例:数组{1,2,3,4,-5,10,-1,-1}的最大连续子数组和是子数组{1,2,3,4,-5,10}的和15    

思路:

原始数组: arr[1...N]

使用辅助数组:sum[1..N]

sum[0]=max{arr[1],0}

sum[i+1]=max{sum[i]+arr[i+1], arr[i+1]}

标签: arr、sum、数组、连续、求其、面试
  • 回复
隐藏