python 使用切片 动态规划 O(n * logn)

最小子数组和,考虑Python的数组切片功能,只能获取子数组，然后求和，获取最小值,通过动态规划，依次获取data[i:j]

def min_sub_array(data):
min = max = sum(data)
min_list = max_list = data
for i in range(len(data)):
for j in range(i+1,len(data)+1):
sub_list = data[i:j]
sum_sub_array = sum(sub_list)
if sum_sub_array <= min:
min = sum_sub_array
min_list = sub_list
elif sum_sub_array > max:
max = sum_sub_array
max_list = sub_list
return min,min_list,max,max_list

算法复杂度O(n)，使用贪心算法

最小子数组和

def min_sub_array1(data):
min = sum(data)
cur_sum = 0
n = len(data)
for i in range(n):
cur_sum = cur_sum + data[i]
if cur_sum<min:
min = cur_sum
if cur_sum > 0:
cur_sum = 0
return min

最大子数组和

def max_sub_array1(data):
max = sum(data)
cur_sum = 0
n = len(data)
for i in range(n):
cur_sum = cur_sum + data[i]
if cur_sum>max:
max = cur_sum
if cur_sum < 0:
cur_sum = 0
return max

Java 算法复杂度O(n)
public static int minSub(int[] data){
int min = sumArray(data);
int n = data.length;
int cursum = 0;
for(int i = 0;i<n;i++){
cursum = cursum + data[i];
if(cursum<min){
min = cursum;
}
if(cursum >0){
cursum = 0;
}
}
return min;
}
public static int maxSub(int[] data){
int max = sumArray(data);
int n = data.length;
int cursum = 0;
for(int i = 0;i<n;i++){
cursum = cursum + data[i];
if(cursum>max){
max = cursum;
}
if(cursum <0){
cursum = 0;
}
}
return max;
}
public static int sumArray(int[] data){
int sum = 0;
for(int i = 0;i<data.length;i++){
sum = sum + data[i];
}
return sum;
}

public static void main(String[] args) {
    int[] data = {1,2,-1,3,-2,1};
    System.out.println(minSub(data));
    System.out.println(maxSub(data));
}