牛客网每日一练

 1 #
 2 # 
 3 # @param A int整型一维数组 
 4 # @return int整型
 5 #
 6 class Solution:
 7     def maxSubArray(self , A ):
 8         max_sim = A[0]
 9         sim = A[0]
10         if not A :
11             return None
12         for n in A[1:]:
13             if sim<0:
14                 sim = n
15             else:
16                 sim += n
17             max_sim = max(max_sim, sim)
18         return max_sim
19             
20         # write code here

请计算给出的数组（至少含有一个数字）中具有最大和的子数组（子数组要求在原数组中连续）

例如：给出的数组为[−2,0,−3,4,−2,2,2,−5,4],

子数组[−2,0,−3,4,−2,2,2,−5,4],具有最大的和:6.

此题有两种解法

贪心思维，设arr[i]为以元素i结尾的子数组的最大和，那么arr[i] = max(arr[i-1]+nums[i], nums[i])，最大的arr[i]即是答案
分治思维，思路很简单，最大子数组和要么存在于左侧区间，要么存在于右侧区间，要么存在于跨越左右侧的区间

因为此题分类为贪心算法类所以我只用了贪心思维，其实贪心算法的时间复杂度为O(n)，分治法的时间复杂度为O(nlogn)