CPP

find maximum sum in array of contiguous subarrays

#include <iostream>

using namespace std;

int main(){
    //Input Array
    int n;
    cin >> n;
    int arr[n];
    for(int i =0;i< n;i++){
    cin >> arr[i];
    }

    int currentSum = 0;
    int maxSum = INT_MIN;
    //algo
    for (int i = 0; i < n; i++)
    {
        currentSum += arr[i];
        if (currentSum <0)
        {
            currentSum = 0;
        }
        maxSum = max(maxSum, currentSum);
    }
    cout << maxSum << endl;

    return 0;
}

Maximum Subarray sum

 def maxSubArray(self, nums: List[int]) -> int:
        curr_best = overall_best =  nums[0]
        for i in range(1,len(nums)):
            if curr_best>=0:
                curr_best = curr_best + nums[i]
            else:
                curr_best = nums[i]
            if curr_best > overall_best:
                overall_best = curr_best
        return overall_best

find longest subarray by sum

def max_length(s, k):
    current = []
    max_len = -1 # returns -1 if there is no subsequence that adds up to k.
    for i in s:
        current.append(i)
        while sum(current) > k: # Shrink the array from the left, until the sum is <= k.
           current = current[1:]
        if sum(current) == k:
            max_len = max(max_len, len(current))

    return max_len

max subsequence sum in array

def max_subarray(numbers):
    """Find the largest sum of any contiguous subarray."""
    best_sum = 0  # or: float('-inf')
    current_sum = 0
    for x in numbers:
        current_sum = max(0, current_sum + x)
        best_sum = max(best_sum, current_sum)
    return best_sum

maximum sum subarray

public static int SumArray()
{
    var arr = new int[]{ -2, -4, -5, -6, -7, -89, -56 };
    var sum = 0;
    var max = arr[0];
    foreach (var item in arr)
    {
        sum += item;
      // sum = Math.Max(sum,0); resting here will not give  expected output
        max = Math.Max(sum,max);
        sum = Math.Max(sum,0);
    }
    return max;
}

How to find the maximum subarray sum in python?

"""
Implementation of "kadane's algorithm".
It returns the maximum subarray sum for
a given bigger array.
Time complexity: O(n)
Space complexity: O(1)
"""

def kadane_algorithm(array):
    running_sum = array[0]
    max_sum = array[0]
    for idx in range(1, len(array)):
        current_val = array[idx]
        running_sum = max(current_val, running_sum+current_val)
        max_sum = max(max_sum, running_sum)
    return max_sum

print(kadane_algorithm([1, 2, 3, 5, -1]))  # 11 = 1 + 2 + 3 + 5

Maximum subarray sum

var maxSequence = function(arr){
  var min = 0, ans = 0, i, sum = 0;
  for (i = 0; i < arr.length; ++i) {
    sum += arr[i];
    min = Math.min(sum, min);
    ans = Math.max(ans, sum - min);
  }
  return ans;
}

Largest sum contiguous subarray

// Java program to print largest 
// contiguous array sum
class GFG {
  
    static void maxSubArraySum(int a[], int size)
    {
        int max_so_far = Integer.MIN_VALUE,
        max_ending_here = 0,start = 0,
        end = 0, s = 0;
  
        for (int i = 0; i < size; i++) 
        {
            max_ending_here += a[i];
  
            if (max_so_far < max_ending_here) 
            {
                max_so_far = max_ending_here;
                start = s;
                end = i;
            }
  
            if (max_ending_here < 0) 
            {
                max_ending_here = 0;
                s = i + 1;
            }
        }
        System.out.println("Maximum contiguous sum is " 
                           + max_so_far);
        System.out.println("Starting index " + start);
        System.out.println("Ending index " + end);
    }
  
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
        int n = a.length;
        maxSubArraySum(a, n);
    }
}
  
// This code is contributed by  prerna saini

find maximum contiguous Sub arrays

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int arr[n];
    for(int i =0;i< n;i++){
        cin >> arr[i];
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = i; j < n; j++)
        {
            for (int k = i; k <= j; k++)
            {
                cout << arr[k] << " ";
            }
            cout << endl;
        }
        
    }
    

    return 0;
}

Maximum sum subarray of size ‘K’

l=[4,6,10,8,2,1]
ans=0
m=3
for i in range(len(l)+1):
   for j in range(i):
       if len(l[j:i])==m:
          ans=max(ans,sum(l[j:i]))
print(ans) 

Largest Sum Contiguous Subarray in Range

static void update(int arr[], int arrSize, int index, int value)
{
   // Your code here
   arr[index-1]=value;
}

//Funciton to return the Maximum-Sum in the range.
static int query(int arr[], int n, int left, int right) 
{
   // code here
    int curr=arr[left-1];
       int sum=arr[left-1];
       for (int i=left;i<right;i++){
           sum=Math.max(arr[i], sum+arr[i]);
           curr=Math.max(curr,sum);
       }
       return curr;
}