用lua从写一次最大子数组问题
发布时间:2020-12-14 22:16:33 所属栏目:大数据 来源:网络整理
导读:这回由于Lua 的语法比较强大,所以直接写出代码 别的不多说了,我们可以看到lua写这种逻辑是多么有快感。可以返回多个值,使算法看起来是这么的自然。 附上源代码: function FIND_CROSSING_SUBARRAY (A,low,mid,high)local left_sum = -10000;local sum = 0
这回由于Lua 的语法比较强大,所以直接写出代码 别的不多说了,我们可以看到lua写这种逻辑是多么有快感。可以返回多个值,使算法看起来是这么的自然。 附上源代码: function FIND_CROSSING_SUBARRAY (A,low,mid,high) local left_sum = -10000; local sum = 0; local max_left; local i; for i= mid,-1 do sum = sum + A[i]; if sum>left_sum then left_sum = sum; max_left = i; end end local right_sum = -10000; local sum = 0; local max_right; for j = (mid+1),high,1 do sum = sum + A[j]; if sum >right_sum then right_sum = sum; max_right = j; end end return max_left,max_right,left_sum+right_sum end function FIND_MAXIMUM_SUBARRAY (A,high) if high == low then return low,A[low] else local mid = math.floor((low+high)/2); local left_low,left_high,left_sum = FIND_MAXIMUM_SUBARRAY(A,mid); local right_low,right_high,right_sum= FIND_MAXIMUM_SUBARRAY(A,mid+1,high); local cross_low,cross_high,cross_sum= FIND_CROSSING_SUBARRAY(A,high); if left_sum>=right_sum then if left_sum>=cross_sum then return left_low,left_sum end end if(right_sum>=left_sum)then if (right_sum>=cross_sum) then return right_low,right_sum end end return cross_low,cross_sum end end B={-100,79,89,201,-211,98,99,304,-432}; local left,right,maxvalue= FIND_MAXIMUM_SUBARRAY(B,1,10); print(left," ",maxvalue); (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |