美文网首页
最小子数组和与最大子数组和

最小子数组和与最大子数组和

作者: 柳仁儿 | 来源:发表于2018-10-29 15:16 被阅读0次

    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));
    }
    

    相关文章

      网友评论

          本文标题:最小子数组和与最大子数组和

          本文链接:https://www.haomeiwen.com/subject/knxbtqtx.html