C Program: Pop Sequence

Pop Sequence

Given a stack which can keep $M$ numbers at most. Push $N$ numbers in the order of 1, 2, 3, ..., $N$ and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if $M$M is 5 and $N$N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): $M$ (the maximum capacity of the stack), $N$ (the length of push sequence), and $K$ (the number of pop sequences to be checked). Then $K$ lines follow, each contains a pop sequence of $N$ numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

Sample Input:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

YES
NO
NO
YES
NO

My C program is following.

//Pop Sequence

#include <stdio.h>
#include <stdlib.h>

int possible(int* s, int M, int N);
int maxlessthantemp(int* t, int temp);

int main(void)
{
	int M, N, K, i, j;
	scanf("%d %d %d", &M, &N, &K);
	int* p = (int*)malloc(K * sizeof(int));//To mark whether every one of these K sequences is a possible pop sequence of the stack

        int* seq = (int*)malloc(N * sizeof(int));//To point to a specific sequence
	for (i = 0; i < K; ++i)
	{
		for (j = 0; j < N; ++j)
		{
			scanf("%d", &seq[j]);
		}
		if (possible(seq,M,N))
		{
			p[i] = 1;//Possible pop sequence. Set p[i] to 1
		}
		else
		{
			p[i] = 0;//Impossible. Set p[i] to 0 

                }
	}
	for (i = 0; i < K; ++i)
	{
		if (p[i])
		{
			printf("YES\n");//Possible to pop. Print "YES"
		}
		else
		{
			printf("NO\n");//Impossible to pop. Print "YES"

 		}
	}
	return 0;
}

//To judge whether a specific sequence is possible to pop
int possible(int* s, int M, int N)
{
	int i;
	if (*s > M)
	{
		return 0;//The first element to pop is *s, which means elements 1~*s have been pushed. If the number of elements in the stack(*s) is more than M, this sequence doesn't match related demand

 	}
	int temp = *s;//To mark the popping element. *s is popped now.
	int* t = (int*)malloc(N * sizeof(int));//To mark which element(s) have/has been popped in this sequence
	for (i = 0; i < N; ++i)
	{
		*(t + i) = i+1;//Not popped yet. Set it to related element value
	}
	*(t-1+*s) = 0;//*s is popped. Set *(t-1+*s) to 0
	for (i = 1; i < N; ++i)
	{
		if (*(s + i) < maxlessthantemp(t,temp))
		{
			return 0;//Not proper popping element. Return 0
		}
		/* In the circumstances of *(s + i) > maxlessthantemp(t, temp) (Only pushing operation may cause overflowing, constant popping can not),
		the number of elements currently having been pushed subtracts the number of those elements who have been popped, gaining the number of elements currently in the stack.

                If it's more than M, this sequence can not be popped rightly
		*/
		if (*(s + i) > maxlessthantemp(t, temp)&& *(s + i) - i > M)
		{
				return 0;
		}
		*(t - 1 + *(s + i)) = 0;//Having been popped. Set it to 0
		temp = *(s + i);//To mark the popping element

 	}
	return 1;
}

/*Proper popping element should meet either one of following two conditions:
1.More than the biggist popped element.
2.Less than the biggist popped element, but in this condition, it should be the maximum of those having not been popped.
So, proper popping element in the function possible(int* s, int N) should be more than temp, or the maximum of those haven't been popped among less-than-temp elements.

I defined a function maxlessthantemp(int* t, int temp) to mark the maximum of those haven't been popped among less-than-temp elements, so proper popping element should be at least this value.
*/
int maxlessthantemp(int* t, int temp)
{
	int i;
	//Through the following loops, element i(also *(t+i-1))becomes the maximum of those haven't been popped among less-than-temp elements. Of course, the circumstance i equals 0 should be explained additionally.

	for (i=temp-1;i>0&&*(t+i-1)==0;--i);
	return i;//When i equals 0, set the value to 0
}

LeetCode Online Judge-1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]. 

//Java Program: Two Sum

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] a = new int[2];
        for(int i=0;i<nums.length-1;i++)
        {
            for(int j=i+1;j<nums.length;j++)

            if (nums[i]+nums[j]==target)
            {
                a[0] = i;
                a[1] = j;
                return a;
            }
        }
        return a;
    }
}

//C Program: Two Sum

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int i, j;
    int *a = (int *) malloc(2*sizeof(int));
    for(i=0;i<numsSize-1;i++)
    {
        for(j=i+1;j<numsSize;j++)
        {
            if (nums[i]+nums[j]==target)
            {
                a[0] = i;
                a[1] = j;
                return a;
            }
        }
    }
    return a;
}

//C++ Program: Two Sum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int> result(2);
        
        for(int i=0;i<nums.size()-1;++i) {
            for(int j=i+1;j<nums.size();++j) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        
    }
};

C Program: Maximum Subsequence Sum

Maximum Subsequence Sum

Given a sequence of $K$K integers { $N_1$​​, $N_2$​​, ..., $N_K$​​ }. A continuous subsequence is defined to be { $N_i$​​, $N_{i+1}$, ..., $N_j$​ } where $1 \le i \le j \le K$. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer $K$ ($\le 10000$). The second line contains $K$ numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices $i$ and $j$ (as shown by the sample case). If all the $K$ numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:

10 1 4

I wrote a program like this:

//Maximum Subsequence Sum

#include <stdio.h>
int maxSum(int a[], int K, int &first);
int main(void)
{
 int K, i, first = 0, max, sum = 0;
 scanf("%d", &K);
 if (K>=1&&K<=100000)
 {
  int a[100000];
  for(i=0;i<K;i++)
   scanf("%d",&a[i]);
  max = maxSum(a, K, first);
  if (max>0)
  {
   for(i=first;sum!=max;i++)
    sum += a[i];
  }
  else if (a[first] == 0)
   ++i;
  else
   i = K;
  printf("%d %d %d\n",max,a[first],a[i-1]);
  return 0;
 }
}

int maxSum(int a[], int K, int &first)
{
 int i;
 int ThisSum = 0;
 int MaxSum = 0;
 for(i=K-1;i>=0;--i)
 {
  ThisSum += a[i];
  if (ThisSum>=MaxSum)
  {
   MaxSum = ThisSum;
   first = i;
  }
  else if (ThisSum<0)
  {
   ThisSum = 0;
  }
 }
 return MaxSum;
}

Acturally, I've tried to transform this C program into Java program with the same algorithm, but failed to pass the Online Judge, due to the poor time efficiency of Java compared to C language. Do you hava a good idea? Relative limits are following.

Time Limit: 200ms

Memory limit: 64MB

Code length restriction: 16kB

Expecting your better methods. 

Java Program: Word Length

The program is to read a line of text, which is divided into several words by spaces and ends with '.'. You should output the length of each word in this line of text. The words here have nothing to do with language, which include a variety of symbols. For example, "it's" is a word, whose length is 4. Note that there may be continuous spaces in the row.

 

Input format:

 

Enter a line of text ending with '.' in a row, but '.' can not be calculated in the last word length.

 

Output format:

 

Output the lengths of each word corresponding to this line of text in one line, every 2 length divided by a space. There are no spaces at the end of the line.

 

Input sample:

 

It's great to see you here.

 

Output sample:

4 5 2 3 3 4

Here is my program.

 //Word Length

import java.util.Scanner;

public class Main {
   
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int count = 0, i;
        boolean isFirst = true;
        for (i=0;i<s.length()-1;)
        {
            while (s.charAt(i)==(' '))
                i++;
            while (s.charAt(i)!=('.')&&s.charAt(i++)!=(' '))
                count++;
            if (isFirst)
            {
                System.out.print(count);
                isFirst = false;
            }
            else
                System.out.print(" "+count);
            count = 0;
        }
    }
}