最大和的子数组

import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int maxSubArray (int[] nums) {
        // write code here
        int length = nums.length;
		int[] subArray = new int[length];
		int curMax = nums[0];
		subArray[0] = nums[0];
		for (int i = 1; i < nums.length; i++) {
			subArray[i] = Math.max(nums[i], subArray[i - 1] + nums[i]);
			curMax = Math.max(curMax,subArray[i]);
		}
		return curMax;
    }
}

/**
 * 53. Maximum Subarray
 *   最大子序和 
 *   给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *   示例:
 * 输入: [-2,1,-3,4,-1,2,1,-5,4], 
 * 输出: 6
 *  解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 * 
 * @author shijiacheng
 *
 */
public class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int sum = nums[0];//默认选择第一个数
        int a = nums[0];

        for(int i = 1;i<nums.length;i++) {
            if(a>0) {
                a += nums[i];
            }else {
                a = nums[i];
            }

            if(sum < a) {
                sum = a;
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums =  {-2,1,-3,4,-1,2,1,-5,4};
        int sum = s.maxSubArray(nums);
        System.out.println(sum);
    }
}

public class LianXuSum {
//非递归
public int max(int []array)
{
int []opt=new int[array.length];
opt[0]=array[0];
int t=opt[0];
int max=opt[0];
for(int i=1;i<array.length;++i) { if(t<0) { opt[i]=array[i]; t=opt[i]; } else if(t>=0)
{
opt[i]=opt[i-1]+array[i];
t=opt[i];
}
if(opt[i]>max)
max=opt[i];
}
return max;
}
public static void main(String[] args) {
int[] array = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
//int[] array = {1};

    int max = new LianXuSum().max(array);
    System.out.println(max);
}

}

import java.util.*;
public class Solution {
    public int maxSubArray(int[] A) {
        int n = A.length;
        if(A==null || n==0) return 0;
        int[] dp = new int [n];
        dp[0]=A[0];
        for(int i = 1;i<n;i++){
            dp[i]= Math.max(A[i],dp[i-1]+A[i]);
        }
        Arrays.sort(dp);
        return dp[n-1];
    }
}

Leetcode#53.Maximum Subarray（最大子序和）

package Array;
/**
 * 53.Maximum Subarray（最大子序和）
 * 给定一个序列（至少含有 1 个数），从该序列中寻找一个连续的子序列，使得子序列的和最大。
 * 例如，给定序列 [-2,1,-3,4,-1,2,1,-5,4]，
 * 连续子序列 [4,-1,2,1] 的和最大，为 6。
 */
public class Solution53 {
    public static void main(String[] args) {
        Solution53 solution53 = new Solution53();
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(solution53.maxSubArray(arr));
    }
    /**
     * maxSum 必然是以nums[i](取值范围为nums[0] ~ nums[n-1])结尾的某段构成的，也就是说maxSum的candidate必然是以nums[i]结果的。如果遍历每个candidate，然后进行比较，那么就能找到最大的maxSum了。
     * 假设把nums[i]之前的连续段叫做sum。可以很容易想到:
     * 1\. 如果sum>=0，就可以和nums[i]拼接在一起构成新的sum。因为不管nums[i]多大，加上一个正数总会更大，这样形成一个新的candidate。
     * 2\. 反之，如果sum<0，就没必要和nums[i]拼接在一起了。因为不管nums[i]多小，加上一个负数总会更小。此时由于题目要求数组连续，所以没法保留原sum，所以只能让sum等于从nums[i]开始的新的一段数了，这一段数字形成新的candidate。
     * 3\. 如果每次得到新的candidate都和全局的maxSum进行比较，那么必然能找到最大的max sum subarray.
     * 在循环过程中，用maxSum记录历史最大的值。从nums[0]到nums[n-1]一步一步地进行。
     *
     * [@param nums
     * @return](/profile/547241) */
    public int maxSubArray(int[] nums) {
        int sum = 0; //或者初始化为  sum = INT_MIN 也OK。
        int maxSum = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (sum >= 0) {
                sum += nums[i];
            } else {
                sum = nums[i];
            }
            if (sum > maxSum) {
                maxSum = sum;
            }
        }
        return maxSum;
    }
    /**
     * 遍历array，对于每一个数字，我们判断，（之前的sum + 这个数字） 和 （这个数字） 比大小，如果（这个数字）自己就比 （之前的sum + 这个数字） 大的话，那么说明不需要再继续加了，直接从这个数字，开始继续，因为它自己已经比之前的sum都大了。
     * 反过来，如果 （之前的sum + 这个数字）大于 （这个数字）就继续加下去。
     * 利用动态规划做题。
     * 只遍历数组一遍，当从头到尾部遍历数组A， 遇到一个数有两种选择 （1）加入之前subArray （2）自己另起一个subArray
     * 设状态S[i], 表示以A[i]结尾的最大连续子序列和，状态转移方程如下:
     * S[i] = max(S[i-1] + A[i],A[i])
     * 从状态转移方程上S[i]只与S[i-1]有关，与其他都无关，因此可以用一个变量来记住前一个的最大连续数组和就可以了。
     * 这样就可以节省空间了。
     * 时间复杂度：O(n)     空间复杂度：O(1)
     */
    public int maxSubArray_2(int[] nums) {
        int sum = 0; //或者初始化为  sum = INT_MIN 也OK。
        int maxSum = nums[0];
        //动态规划
        for (int i = 0; i < nums.length; i++) {
            sum = Math.max(sum + nums[i], nums[i]);
            maxSum = Math.max(sum, maxSum);
        }
        return maxSum;
    }
}

public class Solution {
    public int maxSubArray(int[] A) {
        int max = Integer.MIN_VALUE;
        int curSum = 0;
        for (int i = 0; i < A.length; i++) {
            curSum += A[i];
            max = curSum > max ? curSum : max;
            if (curSum < 0)
                curSum = 0;
        }
        return max;
    }
}

/**
	 * 数组分成两部分，那么子向量结果肯能是在左半部份，右半部份，或者是在中间部分，三个中去最大就可以了
	 * @param nums
	 * @param lo
	 * @param hi
	 * @return
	 */
	private static int maxSum2(int[] nums, int lo, int hi) {
		if (lo > hi)	
			return 0;
		if (lo == hi)
			return nums[lo];
		int m = lo + (hi - lo) / 2;

		int lmax = 0;
		int sum = 0;
		for (int i = m; i >= lo; i--) {
			sum += nums[i];
			if (sum > lmax)
				lmax = sum;
		}

		int rmax = 0;
		sum = 0;
		int i = m + 1;
		while (i <= hi) {
			sum += nums[i];
			i++;
			if (sum > rmax)
				rmax = sum;
		}

		return maxThree(maxSum2(nums, lo, m), maxSum2(nums, m + 1, hi), lmax
				+ rmax);
	}

Analysis of this problem:
Apparently, this is a optimization problem, which can be usually solved by DP. So when it comes to DP, the first thing for us to figure out is the format of the sub problem(or the state of each sub problem). The format of the sub problem can be helpful when we are trying to come up with the recursive relation.

At first, I think the sub problem should look like: maxSubArray(int A[], int i, int j), which means the maxSubArray for A[i: j]. In this way, our goal is to figure out what maxSubArray(A, 0, A.length - 1) is. However, if we define the format of the sub problem in this way, it's hard to find the connection from the sub problem to the original problem(at least for me). In other words, I can't find a way to divided the original problem into the sub problems and use the solutions of the sub problems to somehow create the solution of the original one.

So I change the format of the sub problem into something like: maxSubArray(int A[], int i), which means the maxSubArray for A[0:i ] which must has A[i] as the end element. Note that now the sub problem's format is less flexible and less powerful than the previous one because there's a limitation that A[i] should be contained in that sequence and we have to keep track of each solution of the sub problem to update the global optimal value. However, now the connect between the sub problem & the original one becomes clearer:

maxSubArray(A, i) = maxSubArray(A, i - 1) > 0 ? maxSubArray(A, i - 1) : 0 + A[i];

And here's the code

public int maxSubArray(int[] A) { int n = A.length; int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i]; dp[0] = A[0]; int max = dp[0]; for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0); max = Math.max(max, dp[i]);
        } return max;
}

/*
 *从头开始累加，直到和为负。此时前面这段不能给后面的串带来正收益，应舍弃，sum清零
 *然后在开始统计最大的sum.
 */
public class Solution {
    public int maxSubArray(int[] A) {
        if(A.length == 0) return 0;
        int sum = 0, max = A[0];
        for(int i = 0; i < A.length; i++) {
            sum += A[i];
            if(max < sum) max = sum;
            if(sum < 0)	sum = 0;
        }
        return max;        
    }
}