VERY EASY C++ SOLUTION || BASIC ARRAYS || GREEDY || O(N) TC
IntuitionCalculate Distances from origin for each point, and then obeserve where is the dip of these distances occuring. Wherever the dip is occuring, we have t
# Intuition
Calculate Distances from origin for each point, and then obeserve where is the dip of these distances occuring. Wherever the dip is occuring, we have to change that direction.

# Approach
First store all the manhattan difference of each position from the origin in the array(here pos vector).
Then maintain an add-on value, that should be added to each element once a direction has changed. This addon value ensures that change in direction of previous position updates the change in direction of the later position(because of the prvious position).

In the pos vector, if you encouter a dip, then you can change the direction. A dip means that we are moving closer to the origin, which we don't want. So in order to move away from the origin, we change the direction. 
Which direction to move?-> In the same direction as the previous direction. So if you notice a decrement in the pos vector, then update pos[i] to pos[i-1]+1. Also update the addon by adding it to the difference of previous value of pos[i-1] and updated value of pos[i-1]. Now this addon ensures that for any i+1....i+n element, the change of direction of i is maintained(If direction of i changes then direction of i+1...i+n will also change).

**DRY RUN**
For example 2: Our pos vector will be [1,0,1,2,1,2]. Initially our addon=0.
1) We notice a dip from 1->0. So update pos->[1,2,1,2,1,2] (Update 0->2 because we go in same direction as that of previous, so 1+1=2).
addon= updated value of pos[1]- previous value of pos[1]= 2-0=2 
2) Update next element with addon-> [1,2,3,2,1,2]
3) Update next element with addon-> [1,2,3,4,1,2]
4) Update next element with addon-> [1,2,3,4,3,2]
   We notice a dip after updating with addon.  So we go in the same direction as of previous, so update 3 with 4+1=5. Updated pos=[1,2,3,4,5,2]. NOW UPDATE addon AS WELL, AS A NEW CHANGE IN DIRECTION HAS BEEN RECORDED. So addon= addon+(5-3)=2+2=4. Now addon=4.
5) Update next element with addon-> [1,2,3,4,5,6].

Final pos-> [1,2,3,4,5,6]. Hence the farthest distance from origin is 6.


# Complexity
- Time complexity:
O(N)

- Space complexity:
O(N)

# Code
```cpp []
class Solution {
public:
    int maxDistance(string s, int k) {
        vector<int> pos;
        pair<int,int> state={0,0};
        for(int i=0;i<s.length();i++){
            if(s[i]=='N'){
                state.second+=1;
            }
            else if(s[i]=='W'){
                state.first-=1;
            }
            else if(s[i]=='E'){
                state.first+=1;
            }
            else if(s[i]=='S'){
                state.second-=1;
            }
            int temp= abs(state.first)+abs(state.second);
            pos.push_back(temp);
        }
        int n=pos.size();
        int addon=0;
        bool flag=false;
        for(int i=0;i<n-1;i++){
            pos[i+1]+=addon;
            if(pos[i]>pos[i+1] && k>0){
                int in=pos[i+1];
                pos[i+1]=pos[i]+1;
                addon+=pos[i+1]-in;
                k--;
               // flag=true;
            }
        }

        int mymax=0;
        for(int i=0;i<pos.size();i++){
            mymax=max(mymax,pos[i]);
        }
        return mymax;
    }
};
```
['Array', 'Greedy', 'C++']