Important Methods in Data Structure Algorithm

1. Main Function:

The main() function serves as the entry point for the program.

Key Features:

• Menu for Algorithm Selection: Prompts the user to select one of the algorithms:
• Input Array: The user provides the size of the array (n) and its elements. The array is stored in the integer array arr.
• Switch-Case Logic: Based on the user's choice, one of the algorithms is executed:
• Result Display: The result (maximum subarray sum) is printed to the console.

2. Brute Force Implementation:

int maxSubArrayBruteForce(int arr[], int n)

Logic:

• Iterate through all possible subarrays:Start from each element in the array (i).Expand the subarray to include subsequent elements (j).Compute the sum of the current subarray and update maxSum if it’s greater than the current maxSum.

Complexity:

• Time Complexity: O(n2)O(n^2)O(n2) due to the nested loops.
• Space Complexity: O(1)O(1)O(1), as it uses only a few variables.

3. Divide and Conquer Implementation:

int maxSubArrayDivideAndConquer(int arr[], int left, int right)

Logic:

• Divide: Recursively split the array into two halves.
• Conquer: Find:The maximum subarray sum in the left half.The maximum subarray sum in the right half.The maximum subarray sum crossing the midpoint (using the helper function maxCrossingSum).
• Combine: Return the maximum of the three sums.

Helper Function:

int maxCrossingSum(int arr[], int left, int mid, int right)

Calculates the maximum subarray sum that crosses the midpoint by expanding leftward and rightward from mid.

Complexity:

• Time Complexity: O(nlogn)O(n \log n)O(nlogn) because the array is divided into halves, and each division takes O(n)O(n)O(n) to merge results.
• Space Complexity: O(logn)O(\log n)O(logn) due to the recursive function calls.

4. Kadane's Algorithm Implementation:

int maxSubArrayKadane(int arr[], int n)

Logic:

• Maintain two variables:currentSum: The sum of the current subarray, which either:Includes the current element.Starts anew with the current element if currentSum is negative.maxSum: Tracks the global maximum sum.
• Iterate through the array:Update currentSum as the maximum of the current element or the sum of currentSum + arr[i].Update maxSum if currentSum exceeds it.

Complexity:

• Time Complexity: O(n)O(n)O(n) as the array is traversed once.
• Space Complexity: O(1)O(1)O(1), as only a few variables are used.

5. Dynamic Programming Implementation:

int maxSubArrayDP(int arr[], int n)

Logic:

• Use a dp[] array where:dp[i] stores the maximum subarray sum ending at index i.
• Formula:dp[i] = max(arr[i], dp[i - 1] + arr[i])The current subarray either starts fresh from arr[i] or continues from the previous subarray.
• Iterate through the array:Compute dp[i] for all elements.Update the maxSum during each iteration.

Complexity:

• Time Complexity: O(n)O(n)O(n), as the array is traversed once.
• Space Complexity: O(n)O(n)O(n), for the dp[] array.

Key Notes:

1. Flexibility: The switch-case approach makes the program modular and user-friendly, allowing users to select an algorithm dynamically.
2. Robustness: Invalid inputs are handled gracefully.
3. Ease of Testing: Each algorithm can be tested independently by rerunning the program and selecting different options.

#include <stdio.h>

#include <limits.h>

int maxSubArrayBruteForce(int arr[], int n);

int maxSubArrayDivideAndConquer(int arr[], int left, int right);

int maxCrossingSum(int arr[], int left, int mid, int right);

int maxSubArrayKadane(int arr[], int n);

int maxSubArrayDP(int arr[], int n);

int main() {

? ? int choice, n;

? ? printf("Choose the algorithm:\n");

? ? printf("1: Brute Force\n");

? ? printf("2: Divide and Conquer\n");

? ? printf("3: Kadane's Algorithm\n");

? ? printf("4: Dynamic Programming\n");

? ? scanf("%d", &choice);

? ? printf("Enter the array size: ");

? ? scanf("%d", &n);

? ? int arr[n];

? ? printf("Enter the array elements:\n");

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

? ? ? ? scanf("%d", &arr[i]);

? ? }

? ? int result = 0;

? ? switch (choice) {

? ? ? ? case 1:

? ? ? ? ? ? result = maxSubArrayBruteForce(arr, n);

? ? ? ? ? ? break;

? ? ? ? case 2:

? ? ? ? ? ? result = maxSubArrayDivideAndConquer(arr, 0, n - 1);

? ? ? ? ? ? break;

? ? ? ? case 3:

? ? ? ? ? ? result = maxSubArrayKadane(arr, n);

? ? ? ? ? ? break;

? ? ? ? case 4:

? ? ? ? ? ? result = maxSubArrayDP(arr, n);

? ? ? ? ? ? break;

? ? ? ? default:

? ? ? ? ? ? printf("Invalid choice!\n");

? ? ? ? ? ? return 1;

? ? }

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

? ? return 0;

}

// Brute Force Implementation

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

? ? int maxSum = INT_MIN;

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

? ? ? ? int currentSum = 0;

? ? ? ? for (int j = i; j < n; j++) {

? ? ? ? ? ? currentSum += arr[j];

? ? ? ? ? ? if (currentSum > maxSum) {

? ? ? ? ? ? ? ? maxSum = currentSum;

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? return maxSum;

}

// Divide and Conquer Implementation

int maxSubArrayDivideAndConquer(int arr[], int left, int right) {

? ? if (left == right) {

? ? ? ? return arr[left];

? ? }

? ? int mid = (left + right) / 2;

? ? int leftSum = maxSubArrayDivideAndConquer(arr, left, mid);

? ? int rightSum = maxSubArrayDivideAndConquer(arr, mid + 1, right);

? ? int crossSum = maxCrossingSum(arr, left, mid, right);

? ? return (leftSum > rightSum) ? ((leftSum > crossSum) ? leftSum : crossSum) : ((rightSum > crossSum) ? rightSum : crossSum);

}

int maxCrossingSum(int arr[], int left, int mid, int right) {

? ? int leftMax = INT_MIN, rightMax = INT_MIN;

? ? int sum = 0;

? ? for (int i = mid; i >= left; i--) {

? ? ? ? sum += arr[i];

? ? ? ? if (sum > leftMax) {

? ? ? ? ? ? leftMax = sum;

? ? ? ? }

? ? }

? ? sum = 0;

? ? for (int i = mid + 1; i <= right; i++) {

? ? ? ? sum += arr[i];

? ? ? ? if (sum > rightMax) {

? ? ? ? ? ? rightMax = sum;

? ? ? ? }

? ? }

? ? return leftMax + rightMax;

}

// Kadane's Algorithm Implementation

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

? ? int maxSum = arr[0];

? ? int currentSum = arr[0];

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

? ? ? ? currentSum = (arr[i] > currentSum + arr[i]) ? arr[i] : currentSum + arr[i];

? ? ? ? maxSum = (maxSum > currentSum) ? maxSum : currentSum;

? ? }

? ? return maxSum;

}

// Dynamic Programming Implementation

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

? ? int dp[n];

? ? dp[0] = arr[0];

? ? int maxSum = dp[0];

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

? ? ? ? dp[i] = (arr[i] > dp[i - 1] + arr[i]) ? arr[i] : dp[i - 1] + arr[i];

? ? ? ? if (dp[i] > maxSum) {

? ? ? ? ? ? maxSum = dp[i];

? ? ? ? }

? ? }

? ? return maxSum;

}