题目：
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
样例
给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6
注意
子数组最少包含一个数
挑战
要求时间复杂度为O(n)
解题：
通过率37%，一定是暴力，时间复杂度O(N3)刷出来的成绩。。。
动态规划求解，*，
下面程序半个暴力吧，时间复杂度O(n2)
Java程序：
public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(ArrayList<Integer> nums) {
// write your code
int maxsum = Integer.MIN_VALUE;
for(int i = 0;i<nums.size();i++){
int sum = 0;
for(int j=i;j<nums.size();j++){
sum+=nums.get(j);
maxsum = Math.max(sum,maxsum);
}
}
return maxsum;
}
}
总耗时: 3227 ms
下面看到一个可以时间复杂度是O(N)，但是只能对最大子数组的和大于0的时候才可以，，，但是最大子数组的和是负的，最大的那个负数就是答案了。
Java程序：
public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(ArrayList<Integer> nums) {
// write your code
int maxsum = Integer.MIN_VALUE;
int sum = 0;
for(int i = 0;i<nums.size();i++){
if ( sum < 0 ){
sum = 0;
}
sum += nums.get(i);
maxsum = Math.max(maxsum, sum);
}
return maxsum;
}
}
总耗时: 1497 ms
Python程序：
class Solution:
"""
@param nums: A list of integers
@return: An integer denote the sum of maximum subarray
"""
def maxSubArray(self, nums):
# write your code here
if nums==None:
return 0
maxsum = -11111110
sum = 0
for i in range(len(nums)):
if sum<0:
sum=0
sum+=nums[i]
maxsum = max(sum,maxsum)
return maxsum
总耗时: 246 ms
动态规划求解：
Python程序：
class Solution:
"""
@param nums: A list of integers
@return: An integer denote the sum of maximum subarray
"""
def maxSubArray(self, nums):
# write your code here
max_ending_here = max_so_far = nums[0]
for x in nums[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far , max_ending_here)
print x,max_ending_here,max_so_far
return max_so_far
上面的max_ending_here是包括当前位置时候的最大值，mas_so_far现阶段的最大值。这里理解的不是很透彻。。。
如：
| nums | -2 | 2 | -3 | 4 | -1 | 2 | 1 | -5 | 3 |
| max_ending_here | -2 | 2 | -1 | 4 | 3 | 5 | 6 | 1 | 4 |
| max_so_far | -2 | 2 | 2 | 4 | 4 | 5 | 6 | 6 | 6 |
Java程序：
public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(ArrayList<Integer> nums) {
// write your code
int max_ending_here = nums.get(0);
int max_so_far = nums.get(0);
for( int i =1 ;i<nums.size(); i++) {
max_ending_here = Math.max( nums.get(i) , nums.get(i) + max_ending_here );
max_so_far = Math.max( max_so_far, max_ending_here);
}
return max_so_far;
}
}
总耗时: 1539 ms