Scribd
Upload
9 views8 pages

Maximize Array Algorithms in C++

The document contains multiple programming tasks related to arrays, including finding maximum consecutive 1's, majority elements, maximum subarray sums, and even-odd subarrays. Each task is accompanied by C++ code implementations demonstrating various algorithms and techniques. Additionally, it covers concepts such as prefix sums, equilibrium points, and sliding window techniques.

Uploaded by

jaher65822
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views8 pages

Maximize Array Algorithms in C++

The document contains multiple programming tasks related to arrays, including finding maximum consecutive 1's, majority elements, maximum subarray sums, and even-odd subarrays. Each task is accompanied by C++ code implementations demonstrating various algorithms and techniques. Additionally, it covers concepts such as prefix sums, equilibrium points, and sliding window techniques.

Uploaded by

jaher65822
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

2/6/25, 10:01 PM OneNote

Day 5(Array Easy Level 2)


Thursday, January 30, 2025 2:12 PM

1. Write a program to find the maximum consecutive 1's in a binary array

#include <iostream>
#include <algorithm>
using namespace std;

int maxConsecutiveOne(bool arr[], int n)


{
int res = 0;
for (int i = 0; i < n; i++)
{
int curr = 0;
for (int j = i; j < n; j++)
{
if (arr[j] == 1)
curr++;
else
break;
}
res = max(res, curr);
}
return res;
}

int main() {
bool arr[] = {1, 1, 0, 1, 1, 1, 0, 1, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Consecutive Ones: " << maxConsecutiveOne(arr, n) << endl;

return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

int maxConsecutiveOnes(bool arr[], int n) {


int res = 0, curr = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] == 0)
curr = 0;
else
{
curr++;
res = max(res, curr);
}
}

return res;
}

int main() {
bool arr[] = {1, 1, 0, 1, 1, 1, 0, 1, 1};
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Maximum Consecutive Ones: " << maxConsecutiveOnes(arr, n) << endl;

return 0;
}

2. Write a program to find the


majority element in an array

#include <bits/stdc++.h>
using namespace std;

void findMajority(int arr[], int n)


{
[Link] 1/8
2/6/25, 10:01 PM OneNote
int maxCount = 0;
int index = -1; // sentinels
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (arr[i] == arr[j])
count++;
}

if (count > maxCount)


{
maxCount = count;
index = i;
}
}

if (maxCount > n / 2)
cout << arr[index] << endl;
else
cout << "No Majority Element" <<
endl;
}

int main()
{
int arr[] = { 1, 1, 2, 1, 3, 5, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
findMajority(arr, n);
return 0;
}

bool isMajority(int a[], int size, int cand) void printMajority(int a[], int size)
#include <bits/stdc++.h>
{ {
using namespace std;
int count = 0; int cand = findCandidate(a, size);
for (int i = 0; i < size; i++) if (isMajority(a, size, cand))
int findCandidate(int a[], int size)
if (a[i] == cand) cout << " " << cand << " ";
{
count++; else
int maj_index = 0, count = 1;
if (count > size / 2) cout << "No Majority Element";
for (int i = 1; i < size; i++)
return 1; }
{
else
if (a[maj_index] == a[i])
return 0; int main()
count++;
} {
else
int a[] = { 1, 3, 3, 1, 2 };
count--;
int size = (sizeof(a)) / sizeof(a[0]);
if (count == 0)
printMajority(a, size);
{
return 0;
maj_index = i;
}
count = 1;
}
}
return a[maj_index];
}

[Link] 2/8
2/6/25, 10:01 PM OneNote

3. Write a program to find the maximum subarray sum


#include <stdio.h>
#include <limits.h>

int maximumSubarraySum(int arr[], int n) {


int maxSum = INT_MIN;

for (int i = 0; i < n; i++)


{
int currSum = 0;
for (int j = i; j < n; j++)
{
currSum += arr[j];
if (currSum > maxSum)
{
maxSum = currSum;
}
}
}
return maxSum;
}

int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);

int result = maximumSubarraySum(arr, n);


printf("Maximum Subarray Sum: %d\n", result);

return 0;
}

#include <stdio.h>
#include <limits.h>

int kadaneAlgorithm(int arr[], int n)


{
int maxSum = INT_MIN, currSum = 0;

for (int i = 0; i < n; i++) {


currSum += arr[i];

if (currSum > maxSum)


maxSum = currSum;

if (currSum < 0)
currSum = 0;

[Link] 3/8
2/6/25, 10:01 PM OneNote
}

return maxSum;
}

int main() {
int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int n = sizeof(arr) / sizeof(arr[0]);

int result = kadaneAlgorithm(arr, n);


printf("Maximum Subarray Sum: %d\n", result);

return 0;
}

Write a program to find the maximum length even-odd subarray


#include <stdio.h>
#include <algorithm>
int maxEvenOdd(int arr[], int n)
{
int res = 1;

for (int i = 0; i < n; i++)


{
int curr = 1; // Start with length 1
for (int j = i + 1; j < n; j++)
{
if ((arr[j] % 2 == 0 && arr[j - 1] % 2 != 0) || (arr[j] % 2 != 0 && arr[j - 1] % 2 == 0))
{
curr++;
}
else
{
break; // If condition fails, stop this sequence
}
}

res = std::max(res, curr); // Update the result with the longest found sequence
}
return res;
}

int main() {
int arr[] = {5, 10, 20, 6, 3, 8, 7, 1, 6, 12};
int n = sizeof(arr) / sizeof(arr[0]);

int result = maxEvenOdd(arr, n);


printf("Length of the longest alternating even-odd subarray: %d\n", result);

return 0;
}

#include <stdio.h>
#include <algorithm>

int maxEvenOddOptimized(int arr[], int n) {


int res = 1, curr = 1;

for (int i = 1; i < n; i++)


{
if ((arr[i] % 2 == 0 && arr[i - 1] % 2 != 0) || (arr[i] % 2 != 0 && arr[i - 1] % 2 == 0))
{
curr++; // Increase current length if alternating pattern holds
res = std::max(res, curr);
}
else
{
curr = 1; // Reset count if sequence breaks
}

[Link] 4/8
2/6/25, 10:01 PM OneNote
}

return res;
}

int main() {
int arr[] = {5, 10, 20, 6, 3, 8, 7, 1, 6, 12};
int n = sizeof(arr) / sizeof(arr[0]);

int result = maxEvenOddOptimized(arr, n);


printf("Length of the longest alternating even-odd subarray (Optimized): %d\n", result);

return 0;
}

Write a program to find a subarray with a given sum using the sliding window technique
#include <iostream>
using namespace std;

bool isSubSum(int arr[], int n, int sum)


{
for (int i = 0; i < n; i++) {
int curr = 0;
for (int j = i; j < n; j++) {
curr += arr[j];

if (curr == sum)
return true;
}
}
return false; // If no subarray found, return false
}

int main() {
int arr[] = {1, 4, 20, 3, 10, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 33; // Target sum

if (isSubSum(arr, n, sum))
cout << "Subarray with the given sum exists\n";
else
cout << "No subarray with the

#include <iostream>
using namespace std;

bool isSubSum(int arr[], int n, int sum) {


int s = 0, currSum = 0;

for (int e = 0; e < n; e++)


{
currSum += arr[e];
while (currSum > sum && s <= e)
{
currSum -= arr[s];
s++;
}
if (currSum == sum)
return true;
}

return false; // No such subarray found


}

int main() {
int arr[] = {1, 4, 20, 3, 10, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 33;

[Link] 5/8
2/6/25, 10:01 PM OneNote
if (isSubSum(arr, n, sum))
cout << "Subarray with the given sum exists\n";
else
cout << "No subarray with the given sum exists\n";

return 0;
}

Write a program to find the sum of any subarray using the prefix sum array

#include <iostream>
using namespace std;

void computePrefixSum(int arr[], int n, int prefix[])


{
prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
}
int getSubarraySum(int prefix[], int L, int R) {
if (L == 0)
return prefix[R];
else
return prefix[R] - prefix[L - 1];
}

int main() {
int arr[] = {2, 4, 6, 8, 10, 12};
int n = sizeof(arr) / sizeof(arr[0]);

int prefix[n];
computePrefixSum(arr, n, prefix);

int L = 1, R = 4; // Example query (0-based index)


cout << "Sum of subarray from index " << L << " to " << R << " is: " << getSubarraySum(prefix, L, R) << endl;

return 0;
}

Write a program to find the equilibrium point

#include <iostream>
using namespace std;

bool equilibriumPoint(int arr[], int n)


{
for (int i = 0; i < n; i++) {
int leftSum = 0, rightSum = 0;

for (int j = 0; j < i; j++)


leftSum += arr[j];
for (int k = i + 1; k < n; k++)
rightSum += arr[k];

if (leftSum == rightSum)
return true;
}

[Link] 6/8
2/6/25, 10:01 PM OneNote
return false;
}

int main() {
int arr[] = {1, 3, 5, 2, 2};
int n = sizeof(arr) / sizeof(arr[0]);

if (equilibriumPoint(arr, n))
cout << "Equilibrium Point Exists\n";
else
cout << "No Equilibrium Point Found\n";

return 0;
}

#include <iostream>
using namespace std;

bool equilibriumPoint(int arr[], int n) {


int rs = 0;
for (int i = 0; i < n; i++)
rs += arr[i];

int ls = 0;
for (int i = 0; i < n; i++)
{
rs -= arr[i];

if (ls == rs)
return true;

ls += arr[i]; // Update left sum


}

return false;
}

int main() {
int arr[] = {1, 3, 5, 2, 2};
int n = sizeof(arr) / sizeof(arr[0]);

if (equilibriumPoint(arr, n))
cout << "Equilibrium Point Exists\n";
else
cout << "No Equilibrium Point Found\n";

return 0;
}

Maximum Sum of a Subarray of Size K


#include <stdio.h>
#include <limits.h> // For INT_MIN
int maxSubarraySum(int arr[], int n, int k) {
if (n < k) {
printf("Invalid input: Array size is smaller than subarray size K.\n");
return -1;
}

int curr = 0;

for (int i = 0; i < k; i++)


curr += arr[i];

int res = curr;

for (int i = k; i < n; i++) {


curr = curr + arr[i] - arr[i - k];
if (curr > res)
res = curr; // Update maximum sum
}

return res;
}

// Driver Code

[Link] 7/8
2/6/25, 10:01 PM OneNote
int main() {
int arr[] = {2, 1, 5, 1, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3; // Size of subarray

int maxSum = maxSubarraySum(arr, n, k);

if (maxSum != -1)
printf("Maximum sum of a subarray of size %d: %d\n", k, maxSum);

return 0;
}

[Link] 8/8

You might also like