The Maximum Subarray

Sort by

recency

|

19 Discussions

|

  • + 0 comments

    Java

        public static List<Integer> maxSubarray(List<Integer> arr) {
            int sum = arr.get(0);
            int maxSubSum = sum;
            int sumSequences = sum;
            
            for(int i = 1; i<arr.size(); i++){
                int number =arr.get(i);
                
                sum =Math.max(sum+number, number);
                maxSubSum = Math.max(maxSubSum, sum);
    
                if(sumSequences<0){
                    sumSequences = Math.max(number, sumSequences);
                }else{
                    sumSequences += Math.max(0, number);
                }
                
            }
            
            return Arrays.asList(maxSubSum, sumSequences); 
        }
    
  • + 0 comments

    Pythonic 2 lines:

    def maxSubarray(arr):
        p = [n for n in arr if n > 0]
        return [max(accumulate(arr, lambda s, n: 0 if s+n < 0 else s+n, initial=0)), sum(p)] if p else [max(arr)] * 2
    
  • + 0 comments

    Python

    def getmaxsubsequence(arr):
        total = 0
        for elem in arr:
            if elem > 0:
                total += elem
        return total if total > 0 else max(arr)    
    
    def getmaxsubarray(arr):
        maxbeforeindex = [arr[0]]
        for index in range(1, len(arr)):
            curvalue = arr[index]
            connectedvalue = curvalue + maxbeforeindex[index-1]
            maxbeforeindex.append(max(connectedvalue, curvalue))
        
        return max(maxbeforeindex)
    
    def maxSubarray(arr):
        return [getmaxsubarray(arr), getmaxsubsequence(arr)]
    
  • + 0 comments

    C#

    public static List<int> maxSubarray(List<int> arr)
        {
            int sum = 0;
            int maxSubArrSum = 0;
            int maxSubSeqSum = 0;
            foreach (int num in arr) {
                if (num > 0) maxSubSeqSum += num;
                sum += num;
                if (sum > maxSubArrSum)
                    maxSubArrSum = sum;
                if (sum < 0)
                    sum = 0;
            }
            
            if (arr.All(num => num < 0)) {
                maxSubSeqSum = arr.Max();
                maxSubArrSum = maxSubSeqSum;
            }
            
            return new List<int> { maxSubArrSum, maxSubSeqSum };
        }
    
  • + 0 comments

    JS

    function maxSubarray(array) {
        const getMaxSubsum = array => {
            let maxSum = -Infinity;
            array.reduce((sum, value) => {
                sum += value;
                maxSum = Math.max(maxSum, sum);
                return (sum > 0) ? sum : 0;
            }, 0);
            return maxSum;
        };
        const getMaxSubsequence = array => {
            array.sort((a, b) => a - b);
            return (array.at(-1) < 0) ? array.at(-1) : array.filter(value => value >= 0).reduce((sum, value) => sum + value);
        };
        return [getMaxSubsum(array), getMaxSubsequence(array)];
    }