Lightoj 1433: Minimum Arc Distance

Problem link:[http://lightoj.com/volume_showproblem.php?problem=1433]
Catagory: Adhoc, Mathematics

Explanation:
          S=r*s
here,
          S= Arc length between 2 points in circle
          r= radius of circle
          s= Angle between 2 points in circle
again,
         c^2=a^2 + b ^2 - 2abcos(angle)
         here, a=b=r
         and c=distace between 2 points

so, angle=Inverse_cos((2r^2-c^2)/r^2)

Code:

#include<bits/stdc++.h>
#define ll       long long int
#define SIZE 100005
using namespace std;

double dis(ll x1, ll x2, ll y1, ll y2)
{
          double m=(x1-x2)*(x1-x2);
          double n=(y1-y2)*(y1-y2);

          return sqrt(m+n);

}


int main()
{
          ll o1,o2,a1,a2,b1,b2,l;
          cin>>l;
          ll i=1;
          while(i<=l)
          {
                    cin>>o1>>o2>>a1>>a2>>b1>>b2;
                    double r=dis(o1,a1,o2,a2);
                    double d=dis(a1,b1,a2,b2);
                    double s=acos((2*r*r-d*d)/(2*r*r));
                    cout<<"Case "<<i<<": "<<fixed<<setprecision(8)<<r*s<<"\n";
                    i++;
          }



          return 0;
}

Maximum Sub-array Sum Using Kandane's Algorithm

Problem link:
                     [https://www.interviewbit.com/problems/max-sum-contiguous-subarray/]

Statement:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example:

Given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

For this problem, return the maximum sum.

Catagory: Kandane's Algorithm, Divide and conquer, Bruteforce

Explanation: This problem can be solved either O(n^3),O(n^2) ,O(nlogn) or O(n). Kandane's algorithm is the O(n) solution and i find it so simple and fascinating.

Study Material: codeschool tutorial

                         [https://www.youtube.com/watch?v=ohHWQf1HDfU&feature=youtu.be]

Code:

int Solution::maxSubArray(const vector<int> &A) {

details

    int n=A.size(),s=0,a=INT_MIN,m=INT_MIN;

    for(int i=0; i<n; i++)

    {

        if(s+A[i]>0)

        s+=A[i];

        else

        {

        

        a=max(a,A[i]+s);

            

        s=0;

        continue;

        }

        

        a=max(a,s);

    }

   

    return a;

    

}