Maximum Sum Sub-array (Kadane's Algorithm)

Question: Given an array of integers (both positive and negative), find the sub-array with maximum sum. Example: An array -3, 2, -4, 4, -1, 3, 2, -5, 4 should return the sum as eight, sub-array start index is 3 and sub-array end index is 6.


Time Complexity: O(n)


int
maximum_sum_subarray(int *array, int length, int *max_sum, int *max_start, int *max_end)
{
    int cur_sum = 0, cur_start = 0, cur_end = 0;


    for (cur_end = 0; cur_end < length; cur_end++) {
        cur_sum += array[cur_end];
        if (cur_sum > *max_sum) {
            *max_sum = cur_sum;
            *max_start = cur_start;
            *max_end = cur_end;
        }


        if (cur_sum < 0) {
            cur_sum = 0;
            cur_start = cur_end + 1;
        }
    }
}

Palindrome

Question: Write a program to find whether a given string is a palindrome or not. [A palindrome is a word, phrase, number or other alpha-numeric sequence that can be read the same way in either direction]
Time complexity: O(n)


bool
palindrome (char *str)
{
    int len = (strlen(str) - 1);
    int count = 0;


    for (count = 0; count < len; count++, len--) {
        if (str[count] != str[len]) {
            return (FALSE);
        }
    }


    return (TRUE);
}

Sum of the nodes of binary tree

Question: Write a function to calculate the sum of binary search tree nodes?
Time Complexity: O(n)

int
sum_of_tree_nodes(tree *t)
{
    if (t == NULL) {
        return 0;
    } else {
        return (sum_of_tree_nodes(t->right) +
                t->data                     +
                sum_of_tree_nodes(t->left));
    }
}