UVA 787 - Maximum Sub-sequence Product(java file)

Problem Type : MAX_1D_RANGE_SUM(DP)



import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<BigInteger> list = new ArrayList<BigInteger>();
        BigInteger el, end, pro, maxPro;
        end = new BigInteger("-999999");
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            el = sc.nextBigInteger();
            if (el.compareTo(end) != 0) {
                list.add(el);
            } else {
                maxPro = list.get(0);
                for (int i = 0; i < list.size(); i++) {
                    pro = BigInteger.ONE;
                    for (int j = i; j < list.size(); j++) {
                        pro = pro.multiply(list.get(j));
                        maxPro = maxPro.max(pro);
                    }
                }
                System.out.println(maxPro);
                list.clear();
            }
        }
    }

}

UVA 10684 - The jackpot(cpp file)

Problem Type : Max 1D range sum


Code :
#include<stdio.h>
#define mx 10003

int main()
{
    int test,i,j;
    while(scanf("%d",&test)==1)
    {
        long int max_arr,sum;
        max_arr = 0;
        sum = 0;
        if(test==0)
            break;
        for(i=0; i<test; i++)
        {
            scanf("%d",&j);
            sum+=j;
            if(sum>max_arr)
            {
                max_arr = sum;
            }

            if(sum<0)
            {
                sum=0;
            }

        }
        if(max_arr)
        {
            printf("The maximum winning streak is %ld.\n",max_arr);
        }
        else
        {
            printf("Losing streak.\n");
        }
    }
return 0;
}

UVA 541 - Error Correction(cpp file)

Code :

#include<stdio.h>
#define MAX 102
int main()
{

    int arr[MAX][MAX],test,i,j,tag,corr1,corr2,m,n,sum;
    while(scanf("%d",&test)&&test)
    {
        corr1 = 0;
        corr2 = 0;
        tag =0;
        for(i=1;i<=test;i++)
        {
            sum=0;
            for(j=1;j<=test;j++)
            {
                scanf("%d",&arr[i][j]);
                sum += arr[i][j];
            }
            if(sum%2==1)
            {
               corr1++;
                m=i;
            }
        }
        for(i=1;i<=test;i++)
        {
            sum=0;
            for(j=1;j<=test;j++)
            {
                sum+=arr[j][i];
            }
            if(sum%2==1)
            {
                corr2++;
                n=i;
            }
        }
     //   printf("%d %d\n",corr1,corr2);
       if(corr1==0 && corr2==0)
       {
           printf("OK\n");
       }
      else  if(corr1==1 && corr2==1)
       {
           printf("Change bit (%d,%d)\n",m,n);
       }
       else {

        printf("Corrupt\n");
       }
    }
}

UVA 10739 - String to Palindrome

Problem Type :DP  (Levenshtein distance Algorithm)

Code :

#include<stdio.h>
#include<algorithm>
#include<string.h>
#define mx 1070
using namespace std;
char ch[mx],des[mx];
int arr[mx][mx],cou,len;

void init()
{
    for(int i=0; i<len; i++)
    {
        arr[i][0]=i;
    }
    for(int i=0; i<len; i++)
    {
        arr[0][i]=i;
    }
    return;
}
void lav()
{
    int i,j;
    for(i=1; i<len; i++)
    {
        for(j=1; j<len; j++)
        {
            if(ch[j]==des[i])
            {
                arr[i][j]= arr[i-1][j-1];
            }
            else
            {
            int    p = min(arr[i-1][j],arr[i][j-1]);
                arr[i][j]=min(p,arr[i-1][j-1]);
                arr[i][j]++;
            }
        }
    }
}
int main()
{
    int i,j,test;
    scanf("%d",&test);
    getchar();
    int cas = 0;
    while(test--)
    {
        cas++;
        scanf("%s",ch);
        len = strlen(ch);
        for(i=len; i>=1; i--)
        {
            ch[i]=ch[i-1];
        }
        len++;
        ch[len]='\0';
        des[0]='k';
        j=1;
        for(i=len-1; i>=1; i--)
        {
            des[j]=ch[i];
            j++;
        }
        des[len]='\0';
        cou=0;
        init();
        lav();
        printf("Case %d: %d\n",cas,arr[len-1][len-1]/2);
        memset(arr,0,sizeof arr);
    }
    return 0;
}

UVA 11151 - Longest Palindrome(cpp file)

Algorithm : Edit distance(DP)


#include<stdio.h>
#include<algorithm>
#include<string.h>
#define mx 1070
using namespace std;
char ch[mx],des[mx];
int arr[mx][mx],cou,len;

void init()
{
    for(int i=0; i<len; i++)
    {
        arr[i][0]=i;
    }
    for(int i=0; i<len; i++)
    {
        arr[0][i]=i;
    }
    return;
}
void edit()
{
    int i,j;
    for(i=1; i<len; i++)
    {
        for(j=1; j<len; j++)
        {
            if(ch[j]==des[i])
            {
                arr[i][j]= arr[i-1][j-1];
            }
            else
            {
              arr[i][j] = min(arr[i-1][j],arr[i][j-1]);

                arr[i][j]++;
            }
        }
    }
}
void printlav(int i, int j)
{
    if(i==0 || j==0)
    {
        return;
    }
    else if(ch[j] == des[i])
    {
        cou++;
        printlav(i-1,j-1);
    }
    else
    {
        if(arr[i-1][j]<arr[i][j-1])
        {
            printlav(i-1,j);
        }
        else
        {
             printlav(i,j-1);
        }

    }
}
int main()
{
    int i,j,test;
    scanf("%d",&test);
    getchar();
    while(test--)
    {
        gets(ch);
        if(strlen(ch)==0)
        {
            printf("0\n");
            continue;
        }
        len = strlen(ch);
        for(i=len; i>=1; i--)
        {
            ch[i]=ch[i-1];
        }
        len++;
        ch[len]='\0';
        des[0]='k';
        j=1;
        for(i=len-1; i>=1; i--)
        {
            des[j]=ch[i];
            j++;
        }
        des[len]='\0';
        cou=0;
        init();
        edit();
        printlav(len-1,len-1);

         printf("%d\n",cou);
        memset(arr,0,sizeof arr);
    }
    return 0;
}