题解 | #连续子数组的最大和(二)#

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public List<int> FindGreatestSumOfSubArray (List<int> array) {
        // write code here
        int left = 0;
        int right = 1;
        int dp = array[0];
        int dpLeft = 0;
        int dpRight = 1;
        int max = dp;
        for(int i=1; i< array.Count;i++){
            if(dp+array[i] >= array[i]){
                dp = dp+array[i];
            }else{
                dp = array[i];
                dpLeft = i;
            }
            dpRight = i+1;
            
            if(dp > max){
                left = dpLeft;
                right = dpRight;
                max = dp;
            }else if (dp == max && dpRight- dpLeft > right - left){
                left = dpLeft;
                right = dpRight;
            }
        }
        
        List<int> list = new List<int>(right - left);
        for(int i=left; i< right;i++){
            list.Add(array[i]);
        }
        return list;
    }
}