How DVD chapters were implemented?

   DVD movies contains chapters. The user can browse chapters to view the DVD contents.Once the user has selected the movie chapter, the corresponding movie chapter is played on TV or system.

We might have seen the DVD movie with chapters as follows:
  1) chapter 1,2,3 or play video songs, list of songs in DVD

How it is possible?
   Every chapter has some information like chapter thumbnail [which will be shown while showing the chapter list],
chapter's starting position [milli seconds] in DVD video file.

  When the user has selected the movie chapter, the player application will seek to the chapter's starting position in a video.

  Example:
     chapter 1,120 ms
     chapter 2,360 ms #chapter 2 is starting from 360 ms of the DVD video file whenever the user select this chapter
                      #player application will seek to 360 ms and play the video



Some players have support for moving to next chapter. Usually the player code will have the below logic:

     if ( chapterAvailableForVideo)
     {
         //if chapters are available, next/previous buttons are mapped to switch to next/prev chapter
          map(nextbutton,NextChapter);
          map(prevButton,PrevChapter);
     }
     else
     {
         map(nextButton,forward);
         map(prevButton,rewind);
     }   
   

    onSelectNext()
    {
        if(chapterAvailableForVideo)
         {
              switchTo(nextChapter);  //get next chapter's starting position, seekto this position
                                      // and play video on screen
      }
         else
         {
            doForward();
         }

    }
    onSelectPrev()
    {
        if(chapterAvailableForVideo)
         {
              switchTo(prevChapter);
      }
         else
         {
            doRewind();
         }
     }

Maximum Subarray Sum Source code:

 //maximum crossing subarray
int mcs(int array[],int low, int mid,int high)
{
    result res={0};
    int i =0;
    int left_sum =  -100000;//INT_MIN;
    int right_sum =  -100000;//INT_MIN;
    int sum = 0;
    for(i=mid; i >= 0;i--)
    {
       sum += array[i] ;
       if( sum > left_sum)
       {
            left_sum = sum;
       }

    }

    sum = 0;

    for(i=mid+1; i < high;i++)
    {
       sum += array[i] ;
       if( sum > right_sum)
       {
            right_sum = sum;
       }

    }
   return  left_sum + right_sum;

}

int maximum(int a, int b, int c)
{
    if( (a >= b) && (a >=c))
    {
        return a;
    }
    else if( (b >= a) && (b >=c))
    {
        return b;
    }
    return c;
}

int maxsum(int array[], int low,int high)
{
     int max1,max2,max3;
     if( low == high)
     {
         return array[low];
     }
     int mid = (low +high)/2;
     max1= maxsum(array,low,mid);
     max2= maxsum(array,mid+1, high);
     max3= mcs(array,low,mid,high);

     return maximum(max1,max2,max3);

}

void test()
{
    int array[] = {31,-41,59,26,-53,58,97,-93,-23,84};
    int arraySize = sizeof(array) / sizeof(array[0]) ;
    printf("\n maximum subarray sum=%d",maxsum(array,0,arraySize-1));

}
void main()
{
   test();
}

Different ways to find the magnitude pole of an array:

1) logic: bruteforce
    start from beginning of an array to end of an array and check all the before elements are <= the item and right elements are
> than it.

    O(n^2) Time complexity
    O(1) space complexity

2) logic: If any item is a magnitude pole of an array, then its position wont change after sorting 

   2.1) copy the original array into another array
   2.2) sort  it using o(n^2) insertion/bubble sort or o(n logn) merge sort.
   2.3) Check the original and sorted array  if any item is equal, return the index.
    if no match is found, return -1
  
   O (n log n) time complexity
   O (n) space complexity

   This approach may fail with below inputs:

            2 5 3 1 4
    ascending:  1 2 3 4 5

            2 1 3 5 4   
 

3) logic:If any item is a magnitude pole of an array, then  it will be the maximum and minimum of an array index.

   O(n) time complexity
   O(n) space complexity
  
 3.1) start from beginning and find max of array index[Extra array]
 3.2) start from end and find min of array index [change inplace of original array]
 3.3) Check the max and min array  if any item is equal, return the index.
    if no match is found, return -1
    
   
4) with simple code: o(n) time
                     o(1) space
  int magnitudePole(int a[])
   {
    int i_pole = 0;
    int i_max  = 0;
    bool have_pole = true;
    for (int i = 1; i < N; i++)
    {
        if (A[i] < A[i_pole])
        {
            have_pole = false;
        }
        if (A[i] > A[i_max])
        {
            i_max = i;
            if (!have_pole)
            {
                i_pole = i;
            }
            have_pole = true;
            cout <<endl<< " It has pole @" << i_pole;   
        }
    }
    if( have_pole)
    {
      // cout <<endl<< " It has pole @" << i_pole;   
       return i_pole;
    }
   
    return -1;
   }

5) o(n) time complexity
THis is also similar to max and min approach instead of comparing
min and max arrays, they are using BitSet class to do this job.


 import java.util.BitSet;
public static int magnitudePole(int[] A) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
BitSet bits1 = new BitSet(A.length);
BitSet bits2 = new BitSet(A.length);
for (int i = 0; i < A.length; ++i) {
if (A[i] >= max) {
bits1.set(i);
max = A[i];
}
}
for (int i = A.length - 1; i >= 0; --i) {
if (A[i] <= min) {
bits2.set(i);
min = A[i];
}
}
System.out.println(bits1.toString());
System.out.println(bits2.toString());
bits1.and(bits2);
return bits1.nextSetBit(0);
}