Answers for "Find the contiguous subarray within an array, A of length N which has the largest sum."

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

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

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