连续子数组的最大和(二)

public int[] FindGreatestSumOfSubArray(int[] array) {
        List<Integer> key = new ArrayList<>();
        key.add(array[0]);
        List<Integer> res = new ArrayList<>();
        res.add(array[0]);
        int keyCode = array[0];
        int keyRes = array[0];
        for (int i = 1; i < array.length; i++) {
            if (keyCode + array[i] >= array[i]) {
                keyCode = keyCode + array[i];
            } else {
                keyCode = array[i];
                key.removeAll(key);
            }
            key.add(array[i]);
            if (keyRes < keyCode) {
                keyRes = keyCode;
                res = new ArrayList<>(key);
            }
            if (keyRes == keyCode){
                if (key.size()>res.size()){
                    res = new ArrayList<>(key);
                }
            }
        }
        int[] arrayRes = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            arrayRes[i] = res.get(i);
        }
        return arrayRes;
    }

class Solution {
public:
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        int former = array[0],cur=0;
        //长度为1，直接返回该数组
        if(array.size()==1) return array;
        int res = array[0];
        int pos=0;
        //找到终点
        for(int i=1;i<array.size();i++){
            cur = max(former+array[i],array[i]);
            former=cur;
            if(cur>=res){
                res = cur;
                pos=i;
            }
        }
        int ans=0;
        int start = 0;
        //找起点
        for(int i=pos;i>=0;i--){
            ans+=array[i];
            if(ans==res){
                start=i;
            }
        }
        vector<int>result(array.begin()+start,array.begin()+pos+1);
        return result;
    }
};

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        # write code here
        maxval = array[0]
        temp = array[0]  # 序列累加
        endindex = 1
        beginindex = 0
        for i in range(1, len(array)):
            if temp < 0:
                temp = array[i]
                beginindex = i
            else:
                temp += array[i]
            if temp >= maxval:
                endindex = i
                maxval = temp
        # begin > end 表示 序列全为负
        # begin不断累加， 但此时end已保存最大值索引
        if beginindex > endindex:
            return array[endindex:endindex + 1]
        return array[beginindex:endindex + 1]
                

  public int[] FindGreatestSumOfSubArray(int[] array) {
    if (array == null || array.length == 0) {
      return array;
    }

    int max = array[0], start = 0, end = 0;
    int sum = array[0], start_tmp = 0, end_tmp = 0;
    for (int i = 1; i < array.length; i++) {
      if (sum >= 0) {
        sum = sum + array[i];
        end_tmp = i;
      } else {
        sum = array[i];
        start_tmp = i;
        end_tmp = i;
      }
      if (sum >= max) {
        max = sum;
        start = start_tmp;
        end = end_tmp;
      }
    }

    int[] res = new int[end - start + 1];
    for (int i = 0; i < res.length; i++) {
      res[i] = array[start + i];
    }
    return res;
  }

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        # write code here
        dp = [i for i in array]
        start,end = 0,1
        max_start,max_end = 0,1
#         max_sum = 0
#         df1 = [list(i) for i in array]

        for i in range(1,len(array)):
            
            dp[i] = max(dp[i-1]+array[i],array[i])
            if dp[i-1]+array[i] >= array[i]:
                end += 1
            else:
                start,end = i,i+1
            if sum(array[start:end]) > sum(array[max_start:max_end]):
                max_start,max_end = start,end
            if sum(array[start:end]) == sum(array[max_start:max_end]):
                if len(array[start:end])> len(array[max_start:max_end]):
                    max_start,max_end = start,end
            else:
                max_start,max_end = max_start,max_end
        return array[max_start:max_end]

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        int n = array.size();
        int dp[n];
        int count[n];  //计数数组，用来统计每个位置连续子数组的长度
        vector<int> ans;
        count[0] = 1;
        dp[0] = array[0];
        for(int i = 1; i < n; i++) {
            if(array[i] > dp[i-1] + array[i]) {
                dp[i] = array[i];
                count[i] = 1;
            } else {
                dp[i] = dp[i-1] + array[i];
                count[i] = count[i-1] + 1;
            }
        }
        int k = 0;
        for(int i = 0; i < n; i++) {
            if(dp[i] > dp[k]) {
                k = i;
            }
            if(dp[i] == dp[k]) {
                k = count[i] > count[k] ? i : k;
            }
        }
        for(int i = k - count[k] + 1; i <= k; i++) {
            ans.push_back(array[i]);
        }
        return ans;
    }
};

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindGreatestSumOfSubArray (int[] array) {
        int start = 0;
        int end = 0;
        int max = Integer.MIN_VALUE;
        int len = array.length;
        int temp = 0;

        int dpI = 0;
        int dpIPre = array[0]; //dp[]数组变成dpI和dpIPre
        
        for (int i=1; i<len; i++) {
            /**
             *  dp[]表示包含array[i]的最大子段和, 分两种情况
             * 1. dpIPre + array[i] < array[i]时，去掉dp[i-1], 保留当前array[i]  
             * 2. 在之前子串的情况下，继续增加array[i]        
             */
            if (dpIPre + array[i] < array[i]) {
                dpI = array[i];
                temp = i;
            } else {
                dpI = dpIPre + array[i];
            }

            if (dpI >= max) {
                max = dpI;
                start = temp;
                end = i;
            }

            // 将dp[i-1]赋值成dp[i], 继续loop
            dpIPre = dpI;
        }

        return Arrays.copyOfRange(array, start, end+1);
    }
}

class Solution:
    def FindGreatestSumOfSubArray(self , array: List[int]) -> List[int]:
        result=[]
        curSum=0
        maxSum=0
        begin=0
        for i in range(len(array)):
            if curSum<0:
                curSum=array[i]
                begin=i
            else:
                curSum+=array[i]
            if curSum>maxSum&nbs***bsp;(curSum==maxSum and i+1-begin>len(result)):
                maxSum=curSum
                result=array[begin:i+1]
        if result==[]: return [max(array)]
        else: return result

#include <array>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        int length = array.size();
        if (length <= 1) return array;

        vector<int> result;
        int maxResult = -101;     // 初始最大值
        int currSum = array[0];   // 初始为当前子数组和
        int resultIdx = 0;        // 结果数组对应进入的下标 
        int currStart = 0;        // 当前子数组起始下标
        int maxStart = currStart; // 最大和子数组对应的起始下标

        for (int i = 1; i < length; i ++) {
            int append = currSum + array[i];
            int start = array[i];
            bool isStart = false;
            if (start > append) {
                currSum = start;
                isStart = true;
            } else {
                currSum = append;
            }

            if (isStart) {
                resultIdx = i;
                currStart = i;
            } 
            
            if (currSum >= maxResult) {
                // 头部不同, 进行清空
                if (maxStart != currStart) {
                    result.clear();
                    maxStart = currStart;
                }
                maxResult = currSum;
                while (resultIdx <= i) {
                    result.push_back(array[resultIdx++]);
                }
            }
            
        }
        return result; 
    }
};

#include <climits>
#include <ratio>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型vector
     */
    // dp优化
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        int dp_pre = array[0];
        int res_idx_l = 0;
        int res_idx_h = 0;
        int max_sum = dp_pre;

        int dp = 0;

        int l = 0;
        for (int h = 1; h < array.size(); ++h) {
            dp = std::max(dp_pre + array[h], array[h]);
            if (dp != dp_pre + array[h]) { // array[h] 是子数组的第一个元素
                l = h;
            }


            if (dp > max_sum || (dp == max_sum && h - l > res_idx_h - res_idx_l)) {
                max_sum = dp;

                res_idx_l = l;
                res_idx_h = h;
            }
            
            dp_pre = dp;
        }

        return {array.begin() + res_idx_l, array.begin() + res_idx_h + 1 };
    }

    // dp[i]: [0, i]区间中，以array[i]结尾的子数组的最大和
    // dp[i] = std::max(dp[i-1] + array[i], array[i])

    // 第一版动态规划实现，实现后发现， dp[i]只与dp[i-1]有关，也就是不需要初始化一个O(n)的dp数组
    vector<int> FindGreatestSumOfSubArray2(vector<int>& array) {
        std::vector<int> dp(array.size(), 0);
        dp[0] = array[0];
        int res_idx_l = 0;
        int res_idx_h = 0;
        int max_sum = dp[0];

        int l = 0;
        for (int h = 1; h < array.size(); ++h) {
            dp[h] = std::max(dp[h - 1] + array[h], array[h]);
            if (dp[h] != dp[h - 1] + array[h]) { // array[h] 是子数组的第一个元素
                l = h;
            }


            if (dp[h] > max_sum || (dp[h] == max_sum && h - l > res_idx_h - res_idx_l)) {
                max_sum = dp[h];

                res_idx_l = l;
                res_idx_h = h;
            }
        }

        return {array.begin() + res_idx_l, array.begin() + res_idx_h + 1 };
    }


    // 这个是比较直接的解法，就是最符合直观思路的解法
    vector<int> FindGreatestSumOfSubArray3(vector<int>& array) {
        int max_sum = INT_MIN;
        vector<int> res{};
        int res_idx_l = -1;
        int res_idx_h = -1;

        int cur_sum = 0;
        int l = 0;
        for (int h = 0; h < array.size(); ++h) {
            cur_sum += array[h];
            if (cur_sum > max_sum || (cur_sum == max_sum &&
                                      h - l > res_idx_h - res_idx_l)) {
                max_sum = cur_sum;
                res_idx_l = l;
                res_idx_h = h;
            }

            if (cur_sum < 0) {
                cur_sum = 0;

                l = h + 1;
            }
        }

        return {array.begin() + res_idx_l, array.begin() + res_idx_h + 1 };
    }
};