python 使用切片 動(dòng)態(tài)規(guī)劃 O(n * logn)
最小子數(shù)組和,考慮Python的數(shù)組切片功能,只能獲取子數(shù)組，然后求和，獲取最小值,通過(guò)動(dòng)態(tài)規(guī)劃玻孟，依次獲取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
算法復(fù)雜度O(n)，使用貪心算法
最小子數(shù)組和
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
最大子數(shù)組和
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 算法復(fù)雜度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));
}
