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 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 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; }
kadane algorithm
public int kadane(int[] arr){ int max_so_far = 0, curr_max = Integer.MIN_VALUE; for(int i: arr){ max_so_far += i; if(max_so_far<0) max_so_far = 0; if(max_so_far>curr_max) curr_max = max_so_far; } return curr_max; }
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 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; }