最大和的子数组

/*
 *从头开始累加，直到和为负。此时前面这段不能给后面的串带来正收益，应舍弃，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;        
    }
}

class Solution {
public:
    int maxSubArray(int A[], int n) {
        return divide(A, 0, n-1);
    }
    //分治方法
    int divide(int A[], int left, int right){
        if(left == right){
                return A[left];
        }
        int mid = (left + right)/2;
        //假设最大子序列和的部分全在左边或右边
        int max1 = divide(A, left, mid),max2 = divide(A, mid + 1, right);
        //如果跨过中间，前半部分必须以mid结尾，后半部分开头必须是mid+1
        int max3 = INT_MIN, tmp = 0;
        for(int i = mid; i >= left; i--){
            tmp += A[i];
            max3 = max(max3, tmp);
        }
        int max4 = INT_MIN, sum = 0;
        for(int i = mid+1; i <= right; i++){
            sum += A[i];
            max4 = max(max4, sum);
        }
        return max(max(max1,max2), max3+max4);
    }
};

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

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

class Solution {
public:
    int maxSubArray(int A[], int n) {
    int sum = A[0], maxSum = A[0];
	for (int i = 1; i < n;i++)
	{
		if (sum < 0)
			sum = 0;//先判断之前的sum能否被这次利用（小于0则抛弃）
		sum += A[i];
		maxSum = max(maxSum, sum);
	}
	return maxSum;
    }
};

/*
最大连续子序列和
例如，给定的数组[−2,1，−3,4，−1,2,1，−5,4 ]，相邻子阵[ 4，−1,2,1 ]拥有最大的总和= 6。点击显示更多的练习。 
更多的实践： 
如果您已经解决了O（n）的解决方案，请尝试使用分而治之的方法编写另一个解决方案，这是比较微妙的。 
*/

/*
分析：动归
*/

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int result=INT_MIN,f=0;
        for(int i=0;i<=n-1;++i){
            f=max(f+A[i],A[i]);
            result=max(result,f);
        }
        return result;
    }
};

class Solution {
public:
    int maxSubArray(int A[], int n) 
    {
        if(n==0)
            return 0;
        else
        {
            int maximum=A[0];
            int cur=0;
            for(int i=0;i<n;++i)
            {
                if(cur>0)
                   cur+=A[i];
                else
                   cur=A[i];
                maximum=max(cur,maximum);
            }
            return maximum;
        }       
    }
};

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int sum=A[0],Max=A[0];
        for(int i=1;i<n;i++)
        {
        	if(sum<0)
        		sum=0;
        	sum += A[i];
        	Max = max(Max,sum);
		}
		return Max;
    }
};

/*
思路1：动态规划

状态定义：
F[i]：以i下标为结尾的子数组中的最大和

此时已知F[i]的值，想知道F[i+1]，怎么做呢？
可以这么想：
如果 F[i]+A[i+1] > A[i+1]，是说明把他们连起来是有利的，那么 F[i+1]=F[i]+A[i+1]
如果 F[i]+A[i+1] < A[i+1]，说明把他们连起来不利，干脆就让A[i+1]作为新的子数组，F[i+1] = A[i+1]

状态转移方程；
F[i] = max(F[i-1]+A[i],A[i]);

*/
/*
class Solution {
public:
    int maxSubArray(int* A, int n) {

        //特殊情况
        if(A==nullptr || n==0){
            return 0;
        }

        vector<int> F(n);
        F[0] = A[0];

        //计算
        for(int i=1;i<n;i++){
            F[i] = max(F[i-1]+A[i],A[i]);
        }
        //F数组保存的是以各个下标为截至的子数组的最大和，因此需要进行升序排序，返沪最大的一个和
        sort(F.begin(),F.end());

        return F[n-1];
    }
};
*/

/*
思路2：贪心

其实和动规的流程差不多，也是：对我有利才吸收，不然我就另起炉灶

*/

class Solution {
public:
    int maxSubArray(int* A, int n) {
        //特殊情况
        if(A==nullptr || n==0){
            return 0;
        }

        //保存当前最大的子数组和，但这里要用数组的首元素作为初始，因为数组中可能都是负数
        int totalMax = A[0];
        //保存当前的子数组和
        int sum = A[0];
        for(int i=1;i<n;i++){
            if(sum+A[i] >= A[i]){
                //对我有利，吸收
                sum += A[i];
            }else{
                //对我不利，我另起炉灶
                sum = A[i];
            }
            //每遍历一个元素，就要判断最大值
            totalMax = max(totalMax,sum);
        }
        
        return totalMax;
    }
};

def maxSubArray(self , A ):
        # write code here
        max_sum = []
        ss = 0
        for i in range(len(A)):
                ss += A[i]
                max_sum.append(ss)
                if ss < 0:
                    ss =0
        if max_ss:
            return max(max_ss)
        else:
            return max(A)

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

func maxSubArray( A []int ) int {
    var sum int
    max := A[0]
    for i:=0;i<len(A);i++{
        if sum < 0{
            sum = 0
        }
        sum +=A[i]
        if sum > max{
            max = sum
        }
    }
    return max
}

两种方法——

1. 贪心思维，设arr[i]为以元素i结尾的子数组的最大和，那么arr[i] = max(arr[i-1]+nums[i], nums[i])，最大的arr[i]即是答案
2. 分治思维，思路很简单，最大子数组和要么存在于左侧区间，要么存在于右侧区间，要么存在于跨越左右侧的区间

显然，贪心法的时间复杂度为O(n)，分治法的时间复杂度为O(nlogn)

一直对“贪心”算法的概念比较模糊（或排斥），可能因为贪心这个词语不是那么正面吧，但这恰恰表明了贪心的核心：每一步都获取当前位置/状态下的最优值。联想到动态规划算法，不也是每一步都获取了当前的最优值吗？但贪心最后的解是每一步最优值中再取最优值（够贪心吧？），而动态规划直接取dp数组的最后一个值即可。

方法一：贪心

//
// Created by jt on 2020/9/3.
//
#include <algorithm>
using namespace std;

class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @return int整型
     */
    int maxSubArray(int* A, int n) {
        // write code here
        int maxVal = A[0];
        for (int i = 1; i < n; ++i) {
            A[i] = max(A[i], A[i-1]+A[i]);
            maxVal = max(maxVal, A[i]);
        }
        return maxVal;
    }
};

方法二：分治

//
// Created by jt on 2020/9/3.
//
#include <iostream>
using namespace std;

class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @return int整型
     */
    int maxSubArray(int* A, int n) {
        // write code here
        return divideAndConquer(A, 0, n-1);
    }

private:
    int divideAndConquer(int *A, int left, int right) {
        if (left > right) return INT32_MIN;
        if (left == right) return A[left];
        int mid = left + (right-left)/2;
        int leftMax = divideAndConquer(A, left, mid);
        int rightMax = divideAndConquer(A, mid+1, right);
        int midMax = A[mid], tmp = A[mid];
        for (int i = mid - 1; i >= left; --i) {
            tmp += A[i];
            midMax = max(tmp, midMax);
        }
        tmp = midMax;
        for (int i = mid + 1; i <= right; ++i) {
            tmp += A[i];
            midMax = max(tmp, midMax);
        }
        return max(midMax, max(leftMax, rightMax));
    }
};

class Solution {
public:
    int maxSubArray(int* A, int n) {
        for (int i = 1; i < n; i++)
            A[0] = max(A[0], A[i] += max(A[i - 1], 0));
        return A[0];
    }
};

import java.util.*;


public class Solution {
    /**
     *
     * @param A int整型一维数组
     * @return int整型
     */
    public int maxSubArray (int[] A) {
        // write code here
        // 最初最大值选取仅含第一个值
        int max = A[0];
        // 遍历选取起始点
        for (int i = 0; i < A.length; i++) {
            int sum = 0;
            // 从当前起始点到数组末尾的子数组
            for (int j = i; j < A.length; j++) {
                sum += A[j];    // 计算从该起始点起的子数组和
                max = Math.max(max, sum); // 如果当前子数组和比max大，刷新max的值
            }
        }
        return max;
        }
    }

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