8. Largest sum contiguous subarray.

8. Largest sum contiguous subarray.

Problem link :- click here

C code

//kadane's algorithm
#include<stdio.h>

int maxSubarraySum(int A[], int n)
{
    int i, cur_sum, max_sum;
    cur_sum = 0;
    max_sum = A[0];

    for(i=0; i<n; i++)
    {
        cur_sum = cur_sum + A[i];
        if(cur_sum > max_sum)
        {
            max_sum = cur_sum;
        }
        if(cur_sum < 0)
        {
            cur_sum = 0;
        }
    }
    return max_sum;
}

void main()
{
    int arr[30];
    int n, i, ans;

    printf("Enter the size of the array\n");
    scanf("%d",&n);
    printf("Enter the elements of the array\n");
    for(i=0; i<n; i++)
        scanf("%d",&arr[i]);

    printf("Given Array\n");
    for(i=0; i<n; i++)
        printf("\t%d",arr[i]);

    ans = maxSubarraySum(arr, n);
    printf("\n\nMaximum sum contiguous sub array of the given array is %d\n", ans);
}

Java code

//largest sum conntiguous subarray
package programs;

import java.util.*;

public class Array__8
{
	
	static int max_sum_subarray(int arr[], int n)
	{
		int max_sum, cur_sum;
		max_sum = arr[0];
		cur_sum = arr[0];
		for(int i=1; i<n; i++)
		{
			cur_sum = cur_sum + arr[i];
			if(cur_sum > max_sum)
				max_sum = cur_sum;
			if(cur_sum < 0)
				cur_sum = 0;
		}
		return max_sum;
	}
	
	public static void main(String args[])
	{
		int array[] = new int[20];
		int n, i, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array :");
		n = s.nextInt();
		System.out.println("Enter the elements of the array :");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		System.out.println("Given Array :");
		print_array(array, n);
		System.out.println("\n\n");
		
		ans = max_sum_subarray(array, n);
		System.out.println("Maximum sum of the contiguous subarray is " + ans);
	}

	static void print_array(int arr[], int n)
	{
		for(int i=0; i<n; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity : O(n)
Space complexity : O(1)