Answers for "largest sum contiguous subarray"

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 solution leetcode

def approach3(nums):
    ans = nums[0]
    subarr_sum = nums[0]

    for i in range(1, len(nums)):
        subarr_sum = max(nums[i], nums[i] + subarr_sum)
        ans = max(ans, subarr_sum)

    return ans

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;
}

largest subarray of 0's and 1's

public class Solution {

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int maxlen = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = count + (nums[i] == 1 ? 1 : -1);
            if (map.containsKey(count)) {
                maxlen = Math.max(maxlen, i - map.get(count));
            } else {
                map.put(count, i);
            }
        }
        return maxlen;
    }
}

largest subarray of sum k

//variable size sliding window
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cout<<"Enter the size of the array:"<<endl;
    cin>>n;
    int arr[n];
    cout<<"Enter the elements of the array:"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    int k;
    cout<<"enter the sum whose longest subarray you want to find:"<<endl;
    cin>>k;
    int i=0,j=0,sum=0;
    int mx=0;
    while(j<n)
    {
        sum=sum+arr[j];
        if(sum<k)
        {
            j++;
        }
        else if(sum==k)
        {
            mx=max(mx,j-i+1);
            j++;
        }
        else
        {
            while(sum>k)
            {
                sum=sum-arr[i];
                i++;
            }
            j++;
        }
    }
    cout<<mx<<endl;
    return 0;
}