Write an efficient C program to find the sum of contiguous subarray within a one-dimensionalarray of integer which returns the largest sum.Explanation:Lets take the example of array {5,-3, 4}Possible contiguous subarray combinations are{5}, {-3}, {4}, {5,-3}, {-3,4}, {5,-3,4}The contiguous subarray {5,-3,4} has got the largest sum 6Input Constraints:First line : array size (N), where 1<= N<=100Second line : N integers of separated by spaceswhere each number Ni satisfies-10000 <= Ni <=10000Output Constraints:Single integer SUM which is the largest of sum of all possible contiguous subarray

Question

...expand

🧐 Not the exact question you are looking for?Go ask a question

Solution 1

Sure, here is a simple C program using Kadane's algorithm to solve this problem. Kadane's algorithm is a dynamic programming algorithm that is used to find the maximum possible sum of a contiguous subarray in an array.

#include<stdio.h>

int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0];
   int curr_max = a[0];
 
   for (int i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}

int max(int num1, int num2) 
{
    return (num1 > num2 ) ? num1 : num2;
}

int main()
{
   int arr_size;
   scanf("%d", &arr_size);
   
   int arr[arr_size];
   for(int i=0; i<arr_size; i++)
   {
       scanf("%d", &arr[i]);
   }
   
   int max_sum = maxSubArraySum(arr, arr_size);
   printf("Maximum contiguous sum is %d", max_sum);
   
   return 0;
}

This program first reads the size of the array from the user, then reads the array elements. It then calls the maxSubArraySum function which implements Kadane's algorithm to find the maximum sum of a contiguous subarray. The result is then printed to the console.

This problem has been solved

Solution 2

Sure, here is a simple C program using Kadane's algorithm to solve this problem. Kadane's algorithm is a dynamic programming algorithm that is used to find the maximum sum of a contiguous subarray in an array of integers.

#include<stdio.h>

int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0];
   int curr_max = a[0];
 
   for (int i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}

int max(int num1, int num2) 
{
    return (num1 > num2 ) ? num1 : num2;
}

int main()
{
   int n;
   scanf("%d",&n);
   int a[n];
   for(int i=0; i<n; i++)
   {
       scanf("%d",&a[i]);
   }
   int max_sum = maxSubArraySum(a, n);
   printf("Maximum contiguous sum is %d\n", max_sum);
   return 0;
}

This program first reads the size of the array from the user, then reads the array elements. It then calls the function maxSubArraySum to find the maximum sum of a contiguous subarray. The maxSubArraySum function uses Kadane's algorithm to find the maximum sum. The max function is a helper function to find the maximum of two numbers.

This problem has been solved

Similar Questions

Given an integer array arr, write a program to find the subarray which has the largest sum and return its sum.Sample Input:9-2 -1 -3 4 -1 2 1 -5 4Sample Output:6Explanation:The subarray is [4, -1, 2, 1] and the sum is 6

Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer. Example 1:Input: arr = [1,15,7,9,2,5,10], k = 3Output: 84Explanation: arr becomes [15,15,15,9,10,10,10]

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Given an array 𝐴A of size 𝑁N, find the size of the largest subarray of 𝐴A which has an even sum.For example, for the array [2,1,2][2,1,2] the answer is just 11 as the largest subarray with an even sum is [2][2].Note that a subarray is a contiguous part of an array. For the array [1,3,2][1,3,2], some possible subarrays are [1],[2],[1,3],[1,3,2][1],[2],[1,3],[1,3,2]. However, [1,2][1,2] is not a subarray for this array.Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of multiple lines of input.The first line of each test case contains a single integer 𝑁N — the size of the array.The next line contains 𝑁N space-separated integer - 𝐴1,𝐴2,…,𝐴𝑁A 1 ,A 2 ,…,A N .Output FormatFor each test case, output on a new line, the size of the largest subarray with even sum.Constraints1≤𝑇≤501≤T≤501≤𝑁≤501≤N≤501≤𝐴𝑖≤1041≤A i ≤10 4 Sample 1:InputOutput432 1 231 3 262 2 1 1 1 2111340Explanation:Test case 11: The largest subarray with even sum is the subarray [2][2] having size 11.Test case 22: The largest subarray with even sum is the subarray [1,3,2][1,3,2] having size 33.Test case 33: The largest subarray with even sum is the subarray [2,2,1,1][2,2,1,1] having size 44.Test case 44: No subarray has even sum.

You are given an array of size N containing unique integers. Find the size of the largest subarray that can be rearranged to form a contiguous sequence.A contiguous sequence means that the difference of adjacent elements should be 1.Input FormatThe first line of input contains T - the number of test cases. It's followed by 2T lines, the first line contains N - the size of the array. The second line contains the elements of the array.Output FormatFor each test case, print the size of the largest subarray that can be rearranged to form a contiguous sequence, on a new line.Constraints30 points1 <= T <= 1004 <= N <= 10070 points1 <= T <= 1004 <= N <= 1000General Constraints0 <= A[i] <= 105ExampleInput251 3 2 6 590 8 6 5 7 10 3 2 1Output34ExplanationTest-Case 1The largest subarray that can be rearranged to form a contiguous sequence is [1, 3, 2] which can be rearranged to form [1, 2, 3].Test-Case 2The largest subarray that can be rearranged to form a contiguous sequence is [8, 6, 5, 7] which can be rearranged to form [5, 6, 7, 8].

1/3

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.