Largest consecutive Sum

public static void main(String []args)
{
    int a[] = {-2,5,10,-3,5,-10,2,20,1};
    int result[] = new int[a.length];
    result[0] = a[0];
    
    for(int i=1;i<a.length;i++)
    {
        result[i] = (result[i-1] + a[i] > a[i]) ? result[i-1] + a[i] : a[i];
    }
    
    int max = result[0];
    for(int i=1;i<result.length;i++)
    {
        if(result[i] > max)
            max = result[i];
    }

    System.out.println(max);
}

Largest Non-Consecutive Sum

public static void main(String []args)
{
    int a[] = {1,13,10,2,5,9,15,20,8};
    int result[] = new int[a.length];
    result[0] = a[0];
    int max = 0;
    int index = 0;

    for(int i=0; i<a.length; i++)
    {
        max = 0;
        for(int j=0;j<i-1;j++)
        {
            if(result[j] > max)
                max = result[j];
        }
        result[i] = max + a[i];
    }

    for(int i=1; i<result.length; i++)
    {
        if(result[i] > max)
            max = result[i];
    }

    System.out.println(max);
    }
}

Longest common subsequence problem

Given two character arrays, arr1[m] and arr2[n], determine a longest common subsequence among these two arrays.

Dynamic programming to solve it in O(mn) time and space.

LCS[i, j] = LCS[i-1][j-1] + 1                        ; arr1[i] == arr2[j]
               = MAX(LCS[i-1][j], LCS[i][j-1]) ; otherwise

#define MAX(a,b) ((a)>(b))?(a):(b)

int LCS[100][100];

int lcs(char* arr1, int len1, char* arr2, int len2)
{
    int i = 0;
    int j = 0;

    //LCS is 0 when arr2 is NULL
    for(i=0; i <= len1; i++)
        LCS[i][0] = 0;

    //LCS is 0 when arr1 is NULL
    for(j=0; j <= len2; j++)
        LCS[0][j] = 0;

    for(i=1; i <= len1; i++)
    {
        for(j=1; j <= len2; j++)
        {
            if(arr1[i] == arr2[j])
                LCS[i][j] = LCS[i-1][j-1] + 1;
            else
                LCS[i][j] = MAX(LCS[i-1][j], LCS[i][j-1]);
        }
    }

    int temp = LCS[len1][len2];

    return temp;
}

int main()
{
    char* arr1 = "adbcad";
    char* arr2 = "dbacd";

    printf("LCS: %d\n", lcs(arr1, strlen(arr1), arr2, strlen(arr2)));
    return 0;
}

OR

public static void main(String []args)
{
    String a = "ABCDEFGHIJKL";
    String b = "ABCD";
    int max = 0;
    int z=0; // Store the index of the last element of Substring
    int m[][] = new int[a.length()][b.length()];
    for(int i=0;i<a.length();i++)
    {
        m[i][0] = 0;
    }

    for(int i=0;i<b.length();i++)
    {
        m[0][i] = 0;
    }

    for(int i=0;i<a.length();i++)
    {
        for(int j=0;j<b.length();j++)
        {
            if(a.charAt(i) == b.charAt(j))
            {

                if(i==0 || j==0) // If first element is in the substring
                { 
                    m[i][j] = 1;
                }
                else
                {
                    m[i][j] = m[i-1][j-1] + 1;
                }

                if(m[i][j] > max)
                {
                    max = m[i][j];
                    z = j;
                }
            }
        }
    }

    System.out.println(max);
    System.out.println(z);
}

Longest Increasing Subsequence problem

Given an array of integers, determine the longest increasing subsequence (not necessarily contiguous).

Equations:
LIS[i] = MAX( LIS[j] ) + 1; where 0 <= j < i and A[i] > A[j]

#define MAX(a, b) ((a)>(b))?(a):(b)

int LIS[1000];

int lis(int* A, int len)
{
    int i, j;
    int max;

    LIS[0] = 1;

    for(i=1; i < len; i++)
    {
        max = 0;
        for(j=0; j < i; j++)
        {
            if(A[i] > A[j])
                max = MAX(max, LIS[j]);
        }

        printf("max: %d\n", max);

        LIS[i] = max + 1;
    }

    return LIS[len-1];
}

int main()
{
    int A[] = {4, 3, 9, 4 ,1 ,6};

    printf("LIS: %d\n", lis(A, 6));
    return 0;
}