最大子段和

分析

• 暴力算法复杂度是O(N^3)
• 可以对暴力算法进行优化，将时间复杂度降为O(N^2)
• 利用分治算法

代码

暴力算法

前两重循环用i，j分别定义子段的起点与终点，第三重循环计算子段和。

import java.io.*;
import java.util.*;

public class function {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n;
        int a[] = new int[50010];
        n = in.nextInt();
        for(int i=0;i<n;i++) {
            a[i] = in.nextInt(); // 还需要验证是否都是负数
        }
        int res0 = merge(a, 0, n-1);
        int res = enumeration(a,n);
        int res1 = opti_enumeration(a,n);
        System.out.println(res0);
        System.out.println(res);
        System.out.println(res1);
//      out.println(res);
        out.flush();
    }
    public static int enumeration(int[] a,int n) {
        int sum=0;
        int max = 0;
        for(int i=0;i<n;i++) {
            for(int j=i;j<n;j++) {
                for(int k=i;k<=j;k++) {
                    sum+=a[k];
                    if(max < sum)
                        max = sum;
                }
                sum =0;
            }
        }
        return max;
    }

优化暴力算法

第三重循环可以省略，因为它进行了大量的重复计算。根据公式

我们可以对算法进行改进。

public static int opti_enumeration(int[] a,int n) {
        int sum=0;
        int max = 0;
        for(int i=0;i<n;i++) {
            for(int j=i;j<n;j++) {
                sum+=a[j];
                if(max < sum)
                    max = sum;
            }
            sum=0;
        }
        return max;
    }

分治算法

分治思想：
将整个序列等分为两部分a[1,n/2]与a[n/2+1,n]，则最大子段有三种情形：

1. 出现在左半部分
2. 出现在右半部分

3. 跨越左半部分与右半部分，其中一定包括a[n/2]与a[n/2+1]。
   对于情形3，我们可以在a[1,n/2]中计算出s1，在a[n/2+1,n]中计算出s2。s1+s2就是情形3的最大子段和。

   
   

public static int merge(int[] a, int low, int high) {
        if(low >= high)
            return 0 ;
        int mid = (low+high) / 2;
        int left = merge(a, low, mid);  //前半段的最大字段和
        int right = merge(a, mid+1, high);//后半段的最大字段和
        int i=mid;
        int j=mid+1;
        int left_max = 0;
        int right_max = 0;
        int sum=0;
        while(i>=low) {
            sum+=a[i--];
            if(left_max < sum)
                left_max = sum;
        }
        sum = 0;
        while(j<=high) {
            sum += a[j++];
            if(right_max < sum)
                right_max = sum;
        }
        return Math.max(left_max + right_max, Math.max(left, right)); 
    }

参考

[1]动态规划】最大子段和问题，最大子矩阵和问题，最大m子段和问题